|
|
 |
Условие
В стране Нашии есть военные базы, соединённые дорогами. Набор дорог называется важным, если после закрытия этих дорог найдутся две базы, не соединённые путем. Важный набор называется стратегическим, если он не содержит меньшего важного набора. Докажите, что множество дорог, каждая из которых принадлежит ровно одному из двух различных стратегических наборов, образует важный набор.
Решение
Соответствующий граф связен, иначе пустое множество образует
важный набор, но тогда пустое множество – это единственный стратегический
набор, а в условии говорится про два различных стратегических набора.
Рассмотрим некоторый стратегический набор.
Лемма. При закрытии всех дорог этого набора граф баз распадается ровно на две компоненты связности, причём ни одна из дорог внутри каждой из этих частей не будет закрыта.
Доказательство. После закрытия стратегического набора множество всех баз разобьётся на компоненты связности. Так как набор важный, этих компонент не менее двух.
Пусть их хотя бы три. Рассмотрим любую (закрытую) дорогу a, ведущую из одной компоненты связности X в другую компоненту Y
(такая дорога найдётся, так как до закрытия граф был связен). Пусть Z – третья компонента связности. Удалим дорогу a из нашего стратегического набора (то есть не будем её закрывать), тогда получится снова важный набор, так как из компоненты X в компоненту Z нельзя проехать, даже пользуясь дорогой a. Но тогда наш набор – не стратегический. Противоречие.
Рассмотрим любую дорогу внутри одной из компонент связности. Если она
закрыта, то, как и выше, выкинем её из стратегического набора. Останется важный набор – противоречие.
Пусть первый стратегический набор разбивает множество баз на подмножества A и B, а второй – на C и D. Обозначим K = A ∩ C, L = A ∩ D,
M = B ∩ C, N = B ∩ D (см. рис.).
При закрытии первого стратегического набора закрыли все дороги, соединяющие множества K и M, K и N, L и M, L и N, и оставили открытыми дороги, соединяющие множества K с L и M с N. При закрытии второго набора закрыли все дороги, соединяющие множества K и L, K и N, L и M, M и N, и оставили открытыми дороги, соединяющие K с M и L с N.
Итак, множество дорог, принадлежащих ровно одному стратегическому набору, – это все дороги, соединяющие K и L, K и M, L и N, M и N. При закрытии такого набора дорог множество баз распадётся по крайней мере на (непустые) множества K ∪ N и L ∪ M, не соединённые дорогами. Другими словами, мы получим важный набор, что и требовалось.
Замечания
Этот набор не обязательно будет стратегическим – пусть, например, множества K и N непусты, но из K в N не ведёт ни одной дороги.
