ПитерГор 2015

Подсказка 1

Очевидно, что задача на граф. Вершины — города, рёбра — дороги. Просто пытаться фиксировать пучки и искать следующие — плохая затея, мы вообще не будем знать, как ведёт себя граф в таком процессе. Нужно структурировать наш граф. Как мы можем это сделать, зная, что степень каждой вершины хотя бы 2?

Подсказка 2

Это намекает на циклы. Но будем действовать по порядку. Разобьём граф на компоненты связности. В каждой компоненте выделим наибольший по длине простой цикл. Удалим все входящие в них рёбра, запомним эти циклы. У каких-то вершин степень уменьшилась ровно на 2. Хм, интересно, может продолжить делать что-то подобное, пока не придём в "конечную позицию"?

Подсказка 3

Действительно! После этого снова разобьём граф на компоненты (могли появиться новые). Снова в каждой выделим цикл и т.д., пока циклы не закончатся. Интересно, как выглядит это конечная позиция?

Подсказка 4

Степень каждой вершины всегда кратна 2. Значит, в каждой компоненте всегда есть цикл, если есть рёбра (осознайте это). То есть в конце рёбер не останется. Какой из этого вывод можно сделать?

Подсказка 5

Все рёбра графа разбились на непересекающиеся простые циклы. Граф стал гораздо понятнее, через каждую вершину проходит ровно 50 циклов (осознайте это). Но пока не особо понятно, как выбрать из 100 рёбер вершины 10 пучков. Если выбирать произвольно, можно получить пересечения двух пучков из смежных вершин. Хочется, чтобы эти рёбра пучков как бы "смотрели в одну сторону", тогда они точно не совпадут для смежных вершин. Как бы это сделать...?

Подсказка 6

Идея! А давайте ориентируем наши циклы произвольным образом. Тогда из каждой вершины выходит по 50 рёбер и в каждую входит по 50 рёбер. А вот теперь осталось внимательно посмотреть на выходящие рёбра и понять, что если разбить их на пучки, то вы докажите утверждение задачи. Мы в вас верим! Успехов!