|
|
 |
Условие
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на 2N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Решение
Рассмотрим граф G с вершинами в городах, ребра которого
соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в
2N + 2 цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно
утверждению задачи.
Выберем по одному ребру в каждом нечётном цикле графа G. Назовём эти ребра плохими, а остальные – хорошими. Удалив из графа G плохие рёбра, мы получим граф, в котором нет циклов нечётной длины.
Лемма. Вершины графа без нечётных циклов можно раскрасить правильным образом в два цвета.
Доказательство. Достаточно доказать лемму для связного графа. Выберем вершину A и припишем каждой вершине число, равное минимальной длине пути до неё из A. Тогда два одинаковых числа не стоят рядом (иначе есть нечётный цикл). Раскрасив все чётные вершины в один цвет, а нечётные – в другой, получим требуемое.
Таким образом, вершины графа G можно покрасить в два цвета (пусть это цвета a и b) так, что никакие две вершины одного цвета не соединены хорошим ребром.
Поскольку через каждую вершину графа G проходит не более N нечётных циклов, то из каждой вершины выходит не более N плохих рёбер.
Следовательно, мы можем раскрасить вершины графа G в N + 1 цвет так, чтобы никакие две из них не были соединены в графе G плохим ребром. (Будем красить вершины по очереди. Добавляя очередную вершину A, заметим, что среди покрашенных ранее она соединена плохими ребрами не более, чем с N вершинами, следовательно, мы можем покрасить вершину A в цвет, отличный от цветов ранее покрашенных вершин, соединенных с A плохими рёбрами.)
После этого у всех вершин изменим оттенок на светлый, если в первой раскраске она была покрашена в цвет a, и на тёмный, если она была покрашена в цвет b.
В полученной раскраске используется 2N + 2 цвета (с учетом оттенков), и никакие две вершины одного цвета не соединены ребром.
Замечания
Ср. с задачей 110030.
