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