|
|
 |
Условие
В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам, существовавшим в стране до начала всех преобразований. По условию над этим графом несколько раз подряд проделывается следующая операция: удаляются все рёбра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в графе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметь степень 1. Поскольку таких вершин ровно 2002, это даст нам полное решение задачи.
Рассмотрим произвольную вершину v, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее рёбер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции.
Рассмотрим произвольный граф G и вершину u этого графа, при удалении которой образуется связный граф.
Пусть после применения к графу G описанной в условии операции образовался граф G'. Рассмотрим произвольный путь в графе G, не проходящий через u. В графе G' некоторые ребра этого пути могут быть удалены, но их концы должны быть соединены с новой вершиной (обозначим ее w). Таким образом, заменив минимальный участок пути, содержащий все удалённые рёбра, на пару рёбер, соединяющих концы этого участка с вершиной w, мы получим путь в графе G', имеющий те же концы и не проходящий через u. Это означает, что если мы удалим из графа G' вершину u, то для каждых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых (отличных от w) вершин этот путь получается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении u из графа G, а вершина w должна быть соединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины u из графа G' связность сохраняется.
Из доказанного следует, что после всех преобразований при удалении из
получившегося графа вершины v образуется связный граф. Значит, если степень вершины v в получившемся графе больше 1, то между двумя соединёнными с v вершинами есть не проходящий через v путь. Этот путь вместе с вершиной v и двумя выходящими из нее рёбрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степень вершины v в этом графе равна 1.
