4.5. Раскраска граней и вершин. Задача о четырех красках

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

Не меньший интерес представляет доказательство невозможности такой раскраски. (Грани, пересекающиеся в вершинах, не считаются смежными.)

Рис. 4.10.

Рис. 4.11,

Необходимость четырех цветов иллюстрируется рис. 4.10. Гипотеза четырех красок была впервые высказана в лекциях Мёбиуса в 1840 г. и стала хорошо известной благодаря Де Моргану, который получил ее через Ф. Гутри (Fratici Gutrie) приблизительно в 1850 г. В 1878 г. Келей отмечал, что ему не удалось получить строгого доказательства гипотезы. В 1890 г. Хнвуд опроверг ошибочное доказательство, предложенное Кемпс (1879), и доказал достаточность пяти цветов. Прекрасный обзор ранних взглядов на задачу приводится в работе [2].

Упражнение 4.8. Раскрасить четырьмя цветами карту, приведенную на рис. 4.11,

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

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

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

Число смежных граней

Рассмотрим процесс построения граней на плоской карте, при котором каждая грань смежна с возможно большим числом других граней. Начнем с двух смежных граней Для того чтобы построить грань С, соединим ребром точку на границе А с точкой на границе В,

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

Рис. 4.11а.

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

Приведем другое доказательство того, что среднее число ребер, ограничивающих грани карты, меньше шести.

Используем формулу Эйлера, в которой не учтена внешняя грань, т. е. и отношение Отсюда следует, что Если грани нумеруются индексами и если число ребер грани обозначить через то

так как не все ребра принадлежат двум граням, а только некоторые. Следовательно,

Отсюда получаем, что существует, по крайней мере, одна вершина со степенью 5 или меньше.

Другое доказательство справедливости этого факта содержится в доказательстве теоремы 4.21.

Теорема о достаточности пяти красок и другие теоремы

Рассмотрим теоремы, частично иллюстрирующие, как далеко удалось продвинуться в доказательстве гипотезы о четырех красках.

Теорема 4.21. Для раскраски граней плоской карты достаточно пяти цветов.

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

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

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

Теорема 4.22. Для раскраски граней, получаемых ресечением прямых линий на плоскости, достаточно двух цветов.

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

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

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

Упражнения

(см. скан)

(см. скан)

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

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

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

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

Определим вспомогательную целочисленную функцию значения которой по дают требуемую

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

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

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

Тривалентные карты. Однородные карты степени три

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

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

Рис. 4.12.

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

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

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

Теорема 4.25. Если плоский однородный граф степени 3, являющийся -связным (т. е. графом без сочленений), то грани могут быть правильно раскрашены четырьмя цветами тогда и только тогда, когда ребра могут быть правильно окрашены тремя цветами.

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

Воспользуемся следующей таблицей:

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

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

Теорема 4.25 вместе с теоремой 4.26 устанавливает еще одно свойство задачи о раскрашивании четырьмя красками регулярного графа степени 3. Это свойство выражается в терминах чисел, поставленных в соответствие вершинам графа, и впервые было подмечено Хивудом [27]. (См. также [4], гл. 1 и [3], гл. 4.)

Теорема 4.26. Пусть плоский однородный -связ-ный граф степени 3. Тогда ребра могут быть правильно раскрашены тремя цветами тогда и только тогда, когда каждой вершине может быть поставлен в соответствие коэффициент равный или —1, таким образом, что

где суммирование осуществляется по вершинам, расположенным на границе любой грани

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

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

Теоремы 4.25 и 4.26 могут быть также рассмотрены в двойственных понятиях для плоских триангуляций (триангуляционных графов), т. е. плоских графов, в которых каждая грань (включая бесконечную грань) ограничена точно тремя ребрами. Граф, двойственный триангуляционному графу (плоской триангуляции), является -связным, плоским и однородным степени 3; верно и обратное. Правильная -цветная раскраска ребер соответствует в терминах двойственного графа такой -цветной раскраске ребер плоской триангуляции, при которой три ребра, ограничивающие любую грань, будут иметь разные цвета.

(см. скан)

Теорема 4.27. (теорема о трех красках). Грани однородной карты степени 3 могут быть раскрашены тремя цветами тогда и только тогда, когда каждая грань ограничена четным числом ребер.

Доказательство. Необходимость доказывается индукцией по числу граней с использованием доказанного в теореме 4.21 факта о том, что существует, по крайней мере, одна вершина степени не более чем 5. В двойственном графе это означает, что существует, по крайней мере, одна грань, ограниченная самое большее пятью ребрами, так что существует грань, ограниченная точно двумя или четырьмя ребрами. Пусть в случае двухреберной границы будут грани, смежные с рассматриваемой. Если мы удалим одно из двух ограничивающих ребер, удалив тем самым рассматриваемую грань, и устраним вершины степени 2, заменяя их ребра одним ребром, которое инцидентно смежным вершинам, то согласно индуктивному предположению (индукция по числу граней) полученную карту можно окрасить тремя цветами. Введение отброшенной грани требует третьего цвета, который не совпадает ни с одним цветом граней или Случай, когда некоторая грань ограничена четырьмя ребрами и смежна с гранями требует удаления двух противоположных ребер, а также исключения четырех вершин степени 2. Предположим, что удалены ребра, ограничивающие грани Нетрудно показать, что все получившиеся грани имеют четное число ребер и что полученная карта все еще является однородной степени 3 с числом граней, уменьшенным на два. Первоначально грань имела четное число соседних граней, учитывая При раскраске усеченного графа две грани, соседние с которые являются также соседними с как обязательно получат один цвет, так как граням, соседним с должно быть попеременно назначено два цвета. и также получают один цвет, так как они являются частью одной грани в приведенном графе. После возвращения двух удаленных ребер грань может быть окоашена тоетьим. оставшимся цветом.

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

Упражнение 4.15. Сформулировать предыдущую теорему для двойственного графа и доказать ее.

Хроматические полиномы

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

Биркгоф [4], определив значения предложил выражение для в явном виде

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

Упражнения

(см. скан)

Биркгоф [5] показал также, что для карты на сфере

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

Карта называется неприводимой, если все ее грани — связные области, любые две смежные грани образуют простую связную область и любые три грани, которые попарно смежны, образуют простую связную область вокруг вершины степени 3 [8]. Для такой карты

где полиномы относятся к неприводимым картам, и их число

Полная характеристика для различных значений X приводится в работах [8] и [9].