ВсОШ 2023, 11 класс, задача 8
( баллов) В стране городов. В ней действует дорог с односторонним движением: по одной дороге из в для каждой упорядоченной пары городов . У каждой дороги есть цена её обслуживания. Для данного рассмотрим все способы выделить городов и дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём -оптимальной. Докажите, что города можно пронумеровать от до так, что при каждом существует -оптимальная система дорог с выделенными городами . (В. Буслов)
Решение. Рассматриваемые сети из дорог называем далее -сетями. Рассмотрим неориентированный граф, образованный дорогами -сети. В нём не более чем компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее , поскольку рёбер всего не более чем . Поэтому компонент ровно , каждая из них есть дерево, содержит единственный выделенный город и - вспоминая про ориентацию - рёбра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного дорог.
Рассмотрим -оптимальную сеть с выделенными городами и -оптимальную сеть с выделенными городами . Не умаляя общности, ни из одного нельзя добраться в сети до города . Пусть - множество городов, из которых в можно добраться до , а , - множества дорог, выходящих из в сетях , соответственно. Имеем , .
Рассмотрим сеть . Утверждается, что это -сеть для выделенных городов . В самом деле, число дорог в ней равно . Из каждого города, кроме , выходит ровно одна дорога. Выезжая из любого города вне и используя дороги сети, мы по-прежнему можем попасть в один из городов . Выезжая из города в , мы либо попадаем вне - и далее в один из городов , - либо зацикливаемся в . Но тогда содержит цикл, что невозможно.
Рассмотрим сеть . Утверждается, что это -сеть для выделенных городов . В самом деле, , и выезжая из любого города по дорогам сети , мы либо попадаем в - и тогда по доезжаем до , - либо ни разу не попадаем в и тогда доезжаем до одного из городов .
Итак, , - -сеть и -сеть. Сумма их стоимостей такая же, как у и . Значит, они обе оптимальны. Таким образом, для сети удалось выкинуть выделенный город и найти оптимальную -сеть с оставшимися выделенными городами. Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой -сети).