Рассмотрим граф 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 цвета (с учетом оттенков), и никакие две вершины одного цвета не соединены ребром
де )))
Фигуры на плоскости изучают раздел геометрии- планиметрия. Геометрическая фигура-это любое множество точек.
Если все точки геометрической фигуры принадлежат одной плоскости, она называется плоской. Например, отрезок, прямоугольник – это плоские фигуры. Существуют фигуры, не являющиеся плоскими. Это, например, куб, шар, пирамида.
Основные свойства простых фигур выражаются в аксиомах:
Какова бы ни была прямая, существуют точки, принадлежащие этой прямой и не принадлежащие ей.
Через любые две точки можно провести прямую, и только одну.
Из трех точек на прямой одна и только одна лежит между двумя другими.
Этой аксиомой выражается основное свойство расположения точек на прямой.
Каждый отрезок имеет определенную длину, большую нуля. Длина отрезка равна сумме длин частей, на которые он разбивается любой его точкой.
Прямая разбивает плоскость на две полуплоскости.
Этим предложением выражается основное свойство расположения точек относительно прямой на плоскости.
сделай мой ответ лучшим у меня квест .
N=101, и k=3 и n=99, k=100
(но это не точно)
Пошаговое объяснение:
если можно лайк