Условие
В стране Ориентация на всех дорогах введено одностороннее движение, причём из каждого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до любого другого. Докажите, что для каждых двух городов это можно сделать, проехав не более чем по трём дорогам.
Решение
Пусть удалена дорога, ведущая из А в В. Рассмотрим произвольные два города C и D, отличные от А и В.
1) До удаления дороги АВ из C в D можно было проехать по одной или двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому удаление дороги АВ не повлияет на проезд из C в D.
2) После удаления дороги АВ по условию остался путь из A в B. Пусть E – последний город на этом пути перед B. Как показано выше, из C в E можно проехать не более чем по двум дорогам. Значит, из C в B можно проехать не более чем по трём дорогам.
Аналогично доказывается, что из А можно проехать в D не более чем по трём дорогам.
3) До удаления дороги АВ из A в E можно было не более чем по двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому после удаления дороги АВ из А в В можно проехать не более чем по трём дорогам (по маршруту АEВ).
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Генкин С.А., Итенберг И.В., Фомин Д.В. |
|
Год издания |
1994 |
|
Название |
Ленинградские математические кружки |
|
Издательство |
Киров: "АСА" |
|
Издание |
1 |
|
глава |
|
Номер |
13 |
|
Название |
Графы-2 |
|
Тема |
Теория графов |
|
задача |
|
Номер |
053 |
