Закл 2023

Рассматриваемые сети из дорог называем далее -сетями. Рассмотрим неориентированный граф, образованный дорогами -сети. В нём не более чем компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее поскольку рёбер всего не более чем Поэтому компонент ровно каждая из них есть дерево, содержит единственный выделенный город и — вспоминая про ориентацию — рёбра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0 дорог.

Рассмотрим -оптимальную сеть с выделенными городами

и -оптимальную сеть с выделенными городами

Не умаляя общности, ни из одного нельзя добраться в сети до города Пусть — множество городов, из которых в можно добраться до а — множества дорог, выходящих из в сетях соответственно. Имеем

Рассмотрим сеть

Утверждается, что это -сеть для выделенных городов В самом деле, число дорог в ней равно

Из каждого города, кроме выходит ровно одна дорога. Выезжая из любого города вне и используя дороги сети, мы по-прежнему можем попасть в один из городов Выезжая из города в мы либо попадаем вне — и далее в один из городов — либо зацикливаемся в Но тогда содержит цикл, что невозможно.

Рассмотрим сеть

Утверждается, что это -сеть для выделенных городов В самом деле,

и, выезжая из любого города по дорогам сети мы либо попадаем в — и тогда по доезжаем до — либо ни разу не попадаем в и тогда доезжаем до одного из городов

Итак, — -сеть и -сеть. Сумма их стоимостей такая же, как у и Значит, они обе оптимальны. Таким образом, для сети удалось выкинуть выделенный город и найти оптимальную -сеть с оставшимися выделенными городами. Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой -сети).