Задача 30794

Темы:    [ Деревья ] [ Принцип крайнего (прочее) ] [ Индукция (прочее) ]

Сложность: 4 Классы: 8,9,10

Условие

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более  а) 198 перёлетов;  б) 196 перелётов.

Решение

  б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
  Докажем по индукции, что в дереве с n вершинами  (n > 2)  существует обходящий все вершины маршрут длины не более  2n – 4.  База  (n = 3)  очевидна.
  Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины  2n – 6.  Вставив в него кусок ВАВ получим маршрут длины  2n – 4,  обходящий исходное дерево.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	016