Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток.
Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
Решение
Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а рёбрами – верёвочки. В этом графе нужно удалить как можно больше рёбер так, чтобы он остался связным. Будем убирать рёбра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число рёбер в нашем графе в этот момент. Количество вершин осталось тем же – 51·601 = 30651. Число рёбер в дереве на единицу меньше (см. задачу 31098 б), то есть их 30650. Сначала же их было 601·50 + 600·51 = 60650. Таким образом, можно удалить 30000 рёбер (но не более!).