В графе с n вершинами степень каждой вершины не превосходит пяти. Докажите, что вершины можно раскрасить в три цвета так, что ребер с одноцветными
концами будет не более n/2.
Ответы
Ответ:
N=101, и k=3 и n=99, k=100
(но это не точно)
Пошаговое объяснение:
если помог можно лайк
Ответ:
Рассмотрим граф 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 цвета (с учетом оттенков), и никакие две вершины одного цвета не соединены ребром