|
|
 |
Условие
В городе N с каждой станции метро на любую другую можно проехать. Доказать, что одну из станций можно закрыть на ремонт без права проезда через неё так, чтобы с любой из оставшихся станций можно было по-прежнему проехать на любую другую.
Решение
Первый способ. Пусть S – какая-то станция метро, T – самая далекая от S станция, то есть такая, что кратчайший путь из S на T ведёт через большее (или, по крайней мере, не меньшее) число станций, чем кратчайший путь от S до любой другой станции. Закроем теперь станцию T. При этом из S мы по-прежнему сможем проехать на любую другую (не закрытую) станцию U, ибо кратчайший путь из S в U никак не может вести через T – иначе станция V была бы расположена дальше от S, чем станция T. Поэтому, если U и V – две какие угодно отличные от T станции метро, то с одной из них мы заведомо сможем проехать на другую, минуя T (если U и V отличны от S, проедем с U на S, а оттуда – на V.
Второй способ. Выделим в соответствующем графе максимальное дерево и закроем станцию, соответствующую висячей вершине.
