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