Гуляем по графу

Рассмотрим граф, где вершины — перекрёстки, стрелки — дороги. Тогда условие означает, что каждая стрелка входит в цикл длины Заметим для начала, что в любой перекрёсток после посещения администрации можно вернуться: если до администрации мы проедем по вершинам то для ребра есть цикл, возвращающий нас из в для ребра есть цикл, возвращающий нас из в и т.д.

Рассмотрим минимальный маршрут (по количеству стрелок), ведущий от перекрёстка до администрации и обратно. В маршруте “туда” вершины не могут повторяться, так как иначе можно выкинуть цикл из маршрута, что противоречит минимальности. Также и с “обратно”. Тогда в цепочках “туда” и “обратно” не более вершин, т.е. весь маршрут содержит не более стрелок. При этом стрелок может быть только в ситуации, когда ровно вершин в цепочке, а администрация находилась на -й по счёту стрелке в этом маршруте. Докажем от противного, что в такой ситуации есть другой маршрут, содержащий менее стрелок.

Пусть вершины “туда” шли в порядке Если в минимальном маршруте ровно стрелок, то в маршруте “обратно” снова есть вершина Выехав из к администрации, мы не можем попасть в вершины – так как должен быть путь в по двум стрелкам, что противоречит минимальности маршрута “туда”. Следовательно, администрация находится на стрелке При этом не может альтернативного пути из двух стрелок кроме т.к. “туда” опять будет не минимальным. Таким образом, маршрут имеет вид где — какая-то вершина среди первых семи. Но из неё можно попасть в по двум стрелкам — снова противоречие.

Итак, мы доказали, что в кратчайшем маршруте “обратно” нет вершины Следовательно, весь маршрут содержит менее вершин и менее стрелок.