|
|
 |
Условие
В некоторой стране каждые два города соединены либо авиалинией, либо железной дорогой. Докажите, что
а) можно выбрать вид транспорта так, чтобы от каждого города можно было добраться до любого другого, пользуясь только этим видом транспорта;
б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);
в) каждый город обладает свойством из пункта б);
г) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из каждого города до любого другого не более чем с двумя пересадками.
Решение
а) Первый способ. Пусть из некоторого города A нельзя попасть в некоторый город B по железной дороге. Рассмотрим множество M всех городов, в которые можно попасть из города A по железной дороге. Множество городов, не входящих в M, обозначим N. Множество N непусто, поскольку в нём содержится город B. Ясно, что из городов множества M нельзя попасть в города множества N по железной дороге.
Докажем, что из каждого города в любой другой можно попасть авиарейсами.
Если один из городов принадлежит M, а другой – множеству N, то между ними есть прямая авиалиния.
Пусть два города принадлежат M. Тогда из первого города можно попасть авиарейсом в некоторый город множества N, а оттуда (также самолётом) – во второй город.
Аналогично рассматривается случай, когда оба города принадлежат N.
Второй способ. См. г).
б) См. в).
в) Пусть для города X это не так: есть город A, в который из X нельзя долететь за два "хода", и город B, в который из X нельзя доехать на поезде за два "хода" (значит, X и B связаны авиалинией). Пусть A и B связаны авиалинией. Тогда в X из A в можно добраться по воздуху с пересадкой в B. Противоречие.
Аналогично к противоречию приводит и предположение о том, что A и B связаны железной дорогой.
г) Пусть из A в нельзя долететь за три "хода", а из C в D нельзя доехать на поезде за три "хода". Тогда A и B связаны железной дорогой, а C и D – авиалинией.
Пусть A и C связаны железной дорогой. Тогда B и D связаны авиалинией (иначе был бы ж/д маршрут CABD), а A и D – железной дорогой (иначе есть авиамаршрут BDA). Противоречие: есть ж/д маршрут CAD.
Аналогично к противоречию приводит и предположение о том, что A и C связаны авиалинией.
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: "АСА" |
| Издание | 1 |
| глава | |
| Номер | 13 |
| Название | Графы-2 |
| Тема | Теория графов |
| задача | |
| Номер | 036 |
