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