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