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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, почему же чёрных диаметров столько же, сколько и белых? Каждый разноцветный диаметр содержит одинаковое количество белого и чёрного цвета, потому на одноцветные приходится также равное количество этих двух цветов (изначально каждого по ). Но раз так, то количество чёрных и белых диаметров будет одинаковым, чтобы они содержали равное количество разных цветов, что и требовалось.

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