Рассмотрим граф 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 цвета (с учетом оттенков), и никакие две вершины одного цвета не соединены ребром
а)7х+3=5х+1 б)11-7х=-3 в)0,6(х+7)=0,5(х-3)+6,8
7х-5х=1-3 -7х=-3-11 0,6х+4,2=0,5х-1,5+6,8
2х=-2 -7х=-14 0,6х-0,5х=-1,5+6,8-4,2
х=-2:2 х=-14:(-7) 0,1х=1,1
х=-1 х=2 х=1,1:0,1
ответ: -1 ответ: 2 х=11
ответ:11
Пошаговое объяснение:
Как то так если что то не так поправите,но вроде все правельно.С математикой у меня вроде все норм)
