Раскраски графов

(a) Рассмотрим вершину Из неё исходит рёбер, притом хотя бы из них одного цвета. Пусть они соединяют с вершинами и Заметим, что если какие-то две из этих вершин соединены ребром того же цвета, то мы получим нужную тройку вершин. Предположим, что все рёбра между и покрашены в другой цвет. В этом случае — нужная тройка вершин.

(b) Пусть есть вершина, из которой выходит шесть синих рёбер. Тогда рассмотрим вершин, соединённых с ней синими рёбрами. Давайте вспомним известную задачу, которая утверждает, что в компании из человек есть либо трое попарно знакомых, либо трое попарно незнакомых. То есть среди этих вершин есть либо попарно соединённых красными рёбрами, либо синими. Оба случая решают задачу.

В противном случае есть вершина, из которой выходит не более четырёх синих рёбер (из всех девяти вершин не может выходить по пять синих ребер). Тогда из неё выходит по крайней мере четыре красных ребра. Если хотя бы одно из рёбер, соединяющих их концы красное, то есть красный “треугольник”. Если же все они синие, то образовался полный синий граф на четырёх вершинах.

Давайте как-нибудь раскрасим вершины. Рассмотрим произвольную вершину и её соседей. По приницпу Дирихле найдётся цвет в который покрашены не более двух её соседей. Если не цвета и при этом соединена с хотя бы тремя вершинами её цвета, то мы можем её перекрасить в тем самым уменьшив количество одноцветных рёбер. Если делать такие операции, рано или поздно мы получим граф, в котором каждая вершина является концом не более двух одноцветных рёбер. Это даёт требуемое.

Построим граф вершины которого — города, а ребра — авиамаршруты между городами. Будем красить ребра в красный и синий цвета в зависимости от того, какой авиакомпании принадлежит соответствующий маршрут. Требуется доказать, что в построенном графе существуют два непересекающихся нечетных цикла одного цвета.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Если каждое ребро полного графа (граф с -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, то найдется треугольник (цикла длины все стороны (ребра) которого имеют один цвет.

Доказательство. Пусть — вершины графа. Если ребра и окрашены в один цвет, то будем считать, что в этот цвет покрашен угол Пусть — количества соответственно красных и синих ребер, выходящих из вершины Тогда (для всех ) и общее число окрашенных углов

С другой стороны, в каждом «одноцветном» треугольнике все три угла должны быть окрашены в один цвет, а в каждом «неодноцветном» треугольнике есть только один окрашенный угол. Всего есть треугольников и пусть из них одноцветны, тогда откуда что завершает доказательство леммы 1.

___________________________________________________________________________________________________________________________________________________________________

Лемма 2. Если каждое ребро полного графа (граф с -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, и в этом графе нет одноцветного треугольника (цикла длины все ребра которого окрашены в один цвет), то в этом графе есть два непересекающихся (не имеющих общих ребер) цикла, каждый из которых окрашен в один цвет и имеет длину

Доказательство. Пусть — вершины графа. Рассмотрим ребра — если три из них имеют один и тот же цвет, то найдется одноцветный треугольник, что противоречит условию: действительно, пусть — красные, тогда все ребра должны быть синими (иначе получим красный треугольник), но тогда мы имеем синий треугольник. Итак, из каждой вершины выходят по два красных и два синих ребра.

Рассмотрим граф, состоящий из вершин и только красных ребер — в таком графе степень каждой вершины равна а значит, он либо является циклом длины либо разбивается на меньшие циклы. Если разбить граф на вершинах степени на меньшие циклы, то либо получим цикл из вершины (в наших условиях это невозможно), либо одноцветный треугольник, что также исключено (см. выше). Итак, граф на красных ребрах — цикл длины аналогичный вывод делаем для графа на синих ребрах. Лемма 2 доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче: пусть — вершины графа и пусть — одноцветный треугольник в нем (его существование следует из леммы В графе также есть одноцветный треугольник, т.к. количество его вершин не меньше (даже — пусть это треугольник Если эти треугольники окрашены в один цвет, то решение завершено. Если же нет (допустим, — синий, а — красный), то рассмотрим ребра для — всего ребер и, согласно принципу Дирихле, среди них найдутся ребер одного цвета (без ограничения общности будем считать, что синего). Тогда для некоторого найдутся два синих ребра из тройки т.е. меем один синий и один красный треугольники с общей вершиной

Итак, “угол” — синий, а “угол” — красный. Рассмотрим граф Если в нем есть одноцветный треугольник, то решение завершено: берем его и соответствующий ему по цвету или Если в нет одноцветного треугольника, то, согласно лемме в ней найдутся два разноцветных цикла длины — в этом случае берем нужный из этих циклов в качетсве второго циклического маршрута. Доказательство утверждения задачи завершено.

Рассмотрим путь, соединяющий некоторые две вершины возможно включающий в себя выкинутые рёбра. Покажем, что в этом пути любое выкинутое ребро можно заменить последовательностью невыкинутых. Пронумеруем цвета числами от до По условию полностью сохранились рёбра одного цвета: предположим, что в первого. Тогда выкинули по одному ребру каждого из цветов от до Рассмотрим только рёбра первого и второго цветов: до выкидывания из каждой вершины выходило по одному ребру этих цветов. Следовательно, все города разбиваются на циклы. В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла, следовательно, мы можем обойти любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтись без остальных закрытых рейсов.

Заменим каждую белую улицу города на две, синюю и красную, соединив синим цветом концы синих улиц, соседних с белой, а красным цветом — концы соседних с ней красных улиц (см. рис. ). В соответствии с рисунками рис. будем называть белые улицы улицами типов и а их количества обозначим соответственно и В случаях, изображенных на рис. и рис. будем считать, что красная и синяя улицы, которыми мы заменили белую, пересекаются в точке, отличной от вершин ломаных, которыми являются эти улицы.

Теперь все синие улицы образуют несколько многоугольников. Назовем их синими. Аналогично, красные улицы образуют несколько красных многоугольников. Ясно, что границы двух многоугольников разного цвета либо не пересекаются, либо пересекаются в четном числе точек (если границы пересекаются, то граница одного из многоугольников входит внутрь второго столько же раз, сколько и выходит из него). Но число точек пересечения границ многоугольников разного цвета равно числу белых улиц типов и т. е. Значит, число — четное.

Остается заметить, что разность между числом положительных и числом отрицательных перекрестков равна и, следовательно, кратна четырем.

Оценка. Три квадрата при вершине куба образуют цикл соседних квадратов длины Вокруг него образуется ещё один цикл длины из соседних клеток. А вокруг него — цикл длины Взяв вокруг двух противоположных вершин куба по три таких цикла, а вокруг остальных вершин — по два малых цикла, получим непересекающихся нечётных циклов. Поскольку нечётный цикл в два цвета правильно покрасить нельзя, каждый из них содержит чёрную клетку.

Пример. Красим боковые грани куба в шахматном порядке в жёлтый и зелёный. В основаниях красим главные диагонали красным, остальное докрашиваем в шахматном порядке жёлтым и зелёным.

Удалим все вершины из графа и будем возвращать их по одной, крася их, соблюдая условия раскраски. Для очередной вершины покрашено не более её соседей и не более её соседей через одного соседа. Следовательно, есть не более запретов, а значит, мы можем покрасить добавленную вершину с соблюдением условий.

Поскольку степень каждой вершины не более то весь граф можно покрасить правильным образом в цветов. При такой раскраске выберем все вершины самых частовстречающихся цветов. Таких вершин будет хотя бы Получившийся граф можно раскрасить правильным образом в цвета, значит в нем не может быть нечетных циклов. Т.е. мы получили искомый граф.

Введем граф, где вершины — команды, а ребра проводятся, если команды сыграли матч. Заметим, что степень каждой вершины графа равна Также, заметим, что граф не содержит полный подграф на вершинах, ведь за один круг он заполняется не более чем на ребра, кругов а ребер всего а еще граф не является нечетным циклом. Тогда выполнено условие теоремы Брукса, то есть вершины графа можно правильным образом расскрасить в цветов. Тогда какого-то цвета будет хотя бы Тогда выберем вершин одного цвета, они нам подходят.

Выберем произвольную вершину обозначим через вершину, которая отличается от в точности в -ой позиции. Пусть не умаляя общности ребро  — красное. Для обозначим через соседа вершины соединенного с ней красным ребром. Понятно, что так как любые две вершины и отличаются в позициях. Если и отличаются в позиции то соединена синим ребром с Если для некоторого такое то мы нашли цикл длины с чередующимися красными и синими ребрами. В противное случае обозначим для каждого через позицию, в которой отличаются строки и Рассмотрим путь

то есть мы от соседа идем по красному ребру, затем возвращаемся в соседа по синему ребру, затем опять идем по красному и так далее. Рано или поздно мы придем в ту вершину, в которой уже были, причем этой вершиной будет именно сосед так как в вершины на расстоянии от мы приходим только по красным ребрам, а в каждую вершину ведет ровно одно красное ребро. Полученный цикл нам подойдет. Исходя из сказанного выше, ребра в нем чередуются, и его длина не более чем так как каждая его вторая вершина — это сосед причем не

Докажем индукцией по количеству вершин. База для одной вершины очевидна. Рассмотрим теперь граф на вершине. Выкинем какую-нибудь вершину. Оставшийся граф по предположению можно раскрасить нужным образом. Теперь вернём выкинутую вершину. Она соединена не более чем с вершинами. Следовательно, есть цвет, в который не покрашена ни одна из этих вершин. В него и покрасим эту вершину. Получили требуемое.

(a) Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.

Выберем по одному ребру в каждом нечётном цикле графа и удалим их графа. Обозначим полученный граф В нем нет циклов нечётной длины. Любой такой граф можно окрасить в два цвета правильным образом. Зафиксируем одну такую раскраску, и присвоим одному цвету номер а другому номер

Рассмотрим граф, состоящий из удаленных ребер, который мы будем обозначать В нем степень каждой вершины не превосходит так как по условию задачи через каждую вершину в исходном графе проходит не более нечетных циклов. Ясно, что вершины такого графа можно окрасить в цвет. Действительно, вершины можно красить по очереди, и поскольку на каждом этапе окрашиваемая вершина соединена не более чем с уже окрашенными, для нее существует хотя бы один свободный цвет. Зафиксируем одну такую раскраску, и пронумеруем в ней цвета числами от до

Теперь рассмотрим исходный граф На каждой его вершине напишем пару из двух чисел соответствующих ее цвету в графах и По построению, число может быть либо 1, либо 2, а число  – произвольным от до Ясно, что для любых двух вершин, соединенных ребром в графе эти пары различаются хотя бы по одной из координат. Изготовим окраску графа в новые цвета следующим образом: если на вершине написана пара и то окрасим ее в цвет, имеющий номер если то в цвет с номером Нетрудно проверить, что две вершины будут окрашены в один цвет тогда и только тогда, когда написанные на них пары совпали, и значит по замечанию выше построенная окраска является правильной. Также ясно, что число использованных в ней цветов не превосходит что и требовалось.

(b) Рассмотрим граф с вершинами в городах, рёбра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более нечётных циклов. Докажем индукцией по количеству вершин, что вершины такого графа можно покрасить в цвета так, чтобы никакие две вершины одного цвета не были соединены ребром.

База для графа из одной вершины очевидна.

Шаг индукции. Пусть утверждение верно для графа, в котором менее вершин. Рассмотрим граф с вершинами, в котором через каждую вершину проходит не более нечётных циклов. Удалив из этого графа любую вершину и все выходящие из неё рёбра, мы получим граф с вершиной. Очевидно, через каждую вершину графа проходит не более циклов нечётной длины. Тогда покрасим вершины графа в цвета таким образом, чтобы никакие две вершины одного цвета не были соединены ребром (это можно сделать по индуктивному предположению).

Для цвета () рассмотрим граф из всех вершин графа покрашенных в цвета и и всех проведённых между ними рёбер графа Поскольку никакие две вершины одинакового цвета в графе не соединены ребром, то в этом графе нет циклов нечётной длины. Построим граф добавив к графу вершину и все выходящие из неё к вершинам рёбра.

Если для некоторого в графе через вершину не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае мы можем так перекрасить вершины графа (используя лишь цвета и ), чтобы все рёбра в этом графе соединяли пары вершин разных цветов. Так как все остальные вершины графа покрашены в цвета, отличные от и , то и во всём графе никакие две вершины одинакового цвета не соединены ребром.

Остаётся рассмотреть случай, когда для каждого () в графе через вершину проходит хотя бы один цикл нечётной длины. Заметим, что такой нечётный цикл проходит только по вершинам цветов и причём среди них есть хотя бы одна вершина цвета Следовательно, любые два нечетных цикла из графов и проходящие через различны. Таким образом, через вершину проходит хотя бы цикл нечётной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена.

Просуммируем по всем раскраскам графа количество одноцветных копий графа Эту сумму можно вычислить вторым способом, как сумму по всем подграфам входящим в раскрасок, в которых данный подграф является одноцветным. А такое число, разумеется, равно

 – количество способов выбрать подграф  – количество способов выбрать цвет  – количество способов раскрасить оставшиеся ребра.

По принципу Дирихле, существует раскраска графа, в которой число одноцветных подграфов составляет хотя бы

что и требовалось доказать.

Найдем в графе наименьший цикл нечетной длины. Удалим все вершины, принадлежащие этому циклу, и все ребра, исходящие из этих вершин. В оставшемся (не обязательно связном) графе не будет нечетных циклов, т.к. по условию любые два пересекались по вершине. Тогда наш граф двудольный, а значит, мы можем покрасить его в цвета.

Вернем наш цикл вместе со всеми удаленными ребрами. Поскольку этот цикл был наименьшим, то любая вершина цикла была соединена только с двумя вершинами из этого же цикла. Тогда его можно раскрасить в цвета, отличающиеся от предыдущих (одну вершину красим в цвет для остальных вершин чередуем и цвета). Новые цвета не будут мешать раскраске остального графа. Значит, мы смогли покрасить весь граф в цветов правильным образом.

Возьмём какую-нибудь вершину и покрасим её в какой-нибудь цвет, затем возьмём другую вершину и покрасим её в какой-нибудь цвет и так далее. Предположим, что в процессе мы дошли до некоторой вершины которую не получается так, чтобы раскраска удовлетворяла условию. Это означает, что среди вершин, расстояние от которых до не более есть вершины всех цветов. Однако этого не может быть, поскольку по условию соединена не более чем с вершинами, а каждая из этих вершин также соединена не более чем с вершинами (не считая ). Это означает, что всего есть не более вершин, от которых до путь не больше двух. Пришли к противоречию.

Рассмотрим граф, в котором вершины — числа, ребро проводится, если модуль разности этих чисел — простое число. Будем красить каждую компоненту связности этого графа в два цвета: сначала покрасим любую вершину в красный. Затем покрасим всех её соседей в синий. Затем всех соседей синих, которые ещё не покрашены, в красный. Затем соседей красных в синий. И так далее. Легко видеть, что у каждой красной вершины будет хотя бы один синий сосед, а у каждой синей — хотя бы один красный. В каждой компоненте связности выберем цвет, вершин которого не более половины, и подчеркнем вершины этого цвета. Каждая неподчеркнутая вершина будет соединена хотя бы с одной подчеркнутой.

Предположим, что у нас получилось так раскрасить все ребра. Посмотрим на ребра первого цвета. По условию из каждой вершины выходит 54 ребра разных цветов, значит, из каждой вершины выходит ровно по одному ребру первого цвета. Тогда в графе только на таких ребрах (остальные мысленно сотрем) всего 55 вершин со степенью 1 — а мы знаем, что в графе число вершин нечётной степени чётно. Следовательно, наше предположение неверно.

Пусть в графе вершин. Заметим, что всего рёбер в графе не более откуда следует, что есть вершина степени не более (степень = входящие + исходящие рёбра). Удалим её. В новом графе опять найдется вершина степени не более и т.д. Затем начнём возвращать вершины по одной крася очередную вершину так, чтобы раскраска оставалась правильной. Так можно сделать, так как из вновь добавленной вершины выходит и входит не более рёбер в текущем графе на добавленных вершинах, а цветов

Пример. Пусть все школьники дружат между собой. Тогда можно обойтись фруктами и десертом.

Оценка. Раздадим каждому школьнику его фрукт и десерт одновременно. Докажем, что у каждой пары школьников разные пары. Действительно, если школьники дружат, то у них разные фрукты, а если нет, то разные десерты. Следовательно, у школьников будет не менее 170 различных пар фруктов и десертов, а количество этих пар не превышает

Поймём сначала такой факт, что если в графе степень каждой вершины не больше то его вершины можно покрасить в цвет. Действительно это так, будем по очереди красить вершины, и каждый раз у нас будет не более запретов. Тогда вершины графа можно правильным образом покрасить в цвет. Ориентируем каждое ребро от вершины с цветом меньшего номера к вершине с цветом большего номера. Нетрудно понять, что любой путь в полученном графе будет разноцветный, а значит его длина будет не более