|
|
 |
Условие
В стране n городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза.
Решение
Переформулируем задачу на языке графов. Нам дан полный граф с n вершинами, рёбра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей.
Доказательство проведём по индукции. База. Для полного графа с тремя вершинами утверждение очевидно.
Шаг индукции. Рассмотрим полный граф с n + 1 вершиной. Удалим из рассмотрения одну вершину M с выходящими из неё ребрами. Для оставшегося графа с n вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая.
1) Все рёбра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку A1, A2, ..., An. Тогда, удалив ребро A1A2 и соединив вершину M с вершинами A1 и A2, мы получим цикл, состоящий не более чем из двух одноцветных частей.
2) Не все рёбра цикла окрашены в один цвет. Пусть в цикле есть две одноцветные части: A1A2...Am (красная) и AmAm+1...A1 (синяя). Посмотрим на цвет ребра AmM. Если это
ребро красное, то цикл A1A2...AmMAm+1...A1 – искомый, если же оно синее, то искомым будет цикл A1A2...Am–1MAm...A1.
Ответ
Всегда.
