2019-04-29
В городе Лиссе все станции метро связаны между собой, т. е. с любой станции можно проехать (возможно с пересадками) на любую другую. Доказать, что при этом можно закрыть одну станцию метро (без права проезда через нее) так, чтобы с любой из оставшихся станций можно было проехать на любую другую станцию.
Решение:
Пусть $S$ - какая-то станция метро, $T$ - самая далекая от $S$ станция, т. е. такая, что кратчайший путь из $S$ в $Т$ ведет через большее (или, по крайней мере, не меньшее) число станций, чем кратчайший путь от $S$ до любой другой станции. Закроем теперь станцию $T$. При этом из $S$ мы по-прежнему сможем проехать в любую другую (не закрытую) станцию $U$, ибо кратчайший путь из $S$ в $U$ никак не может вести через $T$ - ведь иначе станция $U$ была бы расположена дальше от $S$, чем станция $T$. Поэтому, если $U$ и $V$ - две какие угодно отличные от $T$ станции метро, то из одной из них мы заведомо сможем проехать в другую, минуя $T$: для этого достаточно, например, если $U$ и $V$ отличны от $S$, проехать из $U$ в $S$, а оттуда - в $V$.