Сетка

 Какое наибольшее число верёвочек, соединяющих соседние узлы сетки размера 4x6, можно разрезать, чтобы сетка не распалась на отдельные куски?

 

Ответ: Поскольку горизонтальных отрезков 5*6 = 30, а вертикальных - 7*4 = 28, то всего верёвочек 30+28 = 58. Далее, узелков 5*7 = 35. Поскольку во всяком дереве количество рёбер на 1 меньше количества вершин (см. здесь http://ru.wikipedia.org/wiki/Дерево_(теория_графов)), то останутся неразрезанными 35–1 = 34 верёвочек. Соответственно, будут разрезаны 58–34 = 24 верёвочки.

Ваша оценка: Нет Средняя: 3.7 (16 оценки)


Комментарии

Да здесь можно и без теории графов обойтись, у нас шесть "столбцов" и в каждом по 5 веревочек, если из 5 оставить 1, конструкция не распадется. Значит удаляем из каждого из 6 столбцов 4 веревочки, итого 24.