Теорема о пяти красках

Для плоских карт требуется максимум пять цветов.

Пятицветная карта

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

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

Схема доказательства от противного

Прежде всего, с данной картой ассоциируется простой планарный граф , а именно , в каждую область карты помещается вершина , затем две вершины соединяются ребром тогда и только тогда, когда соответствующие области имеют общую границу. Затем задача переводится в задачу раскраски графа: нужно раскрасить вершины графа так, чтобы ни одно ребро не имело конечных точек одного цвета. ${\displaystyle G}$

Поскольку является простым планарным графом , т. е. он может быть вложен в плоскость без пересекающихся ребер, и у него нет двух вершин, имеющих более одного общего ребра, и у него нет петель, то можно показать (используя эйлерову характеристику плоскости), что у него должна быть вершина, общая не более чем с пятью ребрами. (Примечание: это единственное место, где в доказательстве используется условие пяти цветов. Если этот метод используется для доказательства теоремы о четырех цветах, на этом этапе он не сработает. Фактически, икосаэдрический граф является 5-регулярным и планарным, и, таким образом, не имеет вершины, общей не более чем с четырьмя ребрами.) Найдите такую ​​вершину и назовите ее . ${\displaystyle G}$ ${\displaystyle v}$

Теперь удалим из . Полученный таким образом граф имеет на одну вершину меньше, чем , поэтому мы можем предположить по индукции , что его можно раскрасить только пятью цветами. Если при раскраске не использовались все пять цветов на пяти соседних вершинах , его можно раскрасить цветом, не используемым соседями. Итак, теперь посмотрим на те пять вершин , , , , которые были смежными с в циклическом порядке (который зависит от того, как мы пишем G). Поэтому мы можем предположить, что , , , , раскрашены цветами 1, 2, 3, 4, 5 соответственно. ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{3}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{5}}$ ${\displaystyle v}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{3}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{5}}$

Теперь рассмотрим подграф , состоящий из вершин, окрашенных только в цвета 1 и 3, и соединяющих их ребер. Для ясности, каждое ребро соединяет вершину цвета 1 с вершиной цвета 3 (это называется цепью Кемпе ). Если и лежат в разных связных компонентах , мы можем поменять цвета 1 и 3 на компоненте, содержащей , не влияя на раскраску остальной части . Это освобождает цвет 1 для выполнения задачи. Если же наоборот и лежат в одной и той же связной компоненте , мы можем найти путь в их соединении, состоящий только из вершин цвета 1 и 3. ${\displaystyle G_{1,3}}$ ${\displaystyle G'}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{3}}$ ${\displaystyle G_{1,3}}$ ${\displaystyle v_{1}}$ ${\displaystyle G'}$ ${\displaystyle v}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{3}}$ ${\displaystyle G_{1,3}}$ ${\displaystyle G_{1,3}}$

Теперь обратимся к подграфу , состоящему из вершин, окрашенных только в цвета 2 и 4, и соединяющих их ребер, и применим те же аргументы, что и раньше. Тогда мы либо сможем обратить раскраску 2-4 на подграфе , содержащем и раскрашиваем цвет 2, либо сможем соединить и с путем, состоящим только из вершин цвета 2 и 4. Такой путь пересечет путь 1-3, который мы построили ранее, поскольку через были в циклическом порядке. Это явно абсурдно, поскольку противоречит планарности графа. ${\displaystyle G_{2,4}}$ ${\displaystyle G'}$ ${\displaystyle G_{2,4}}$ ${\displaystyle v_{2}}$ ${\displaystyle v}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{5}}$

Так что на самом деле он может быть пятицветным, вопреки первоначальному предположению. ${\displaystyle G}$

Алгоритм пятицветной раскраски с линейным временем

Несколько авторов, начиная с Липтона и Миллера в 1978 году, изучали эффективные алгоритмы для пятицветной раскраски планарных графов. Алгоритм Липтона и Миллера занял время , ^[1] но последующие исследователи сократили временную границу до . ^{[2] [3] [4] [5] [6]} Версия ниже взята из статьи Робертсона, Сандерса, Сеймура и Томаса 1996 года, в которой она кратко описывается в связи с более медленным алгоритмом для четырехцветной раскраски. ^[7] Описанный здесь алгоритм работает на мультиграфах и полагается на возможность иметь несколько копий ребер между одной парой вершин. Он основан на теореме Вернике , которая утверждает следующее: ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

Теорема Вернике : Предположим, что G плоский, непустой, не имеет граней, ограниченных двумя ребрами, и имеет минимальную степень 5. Тогда G имеет вершину степени 5, которая смежна с вершиной степени не более 6.

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

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

• S ₄ : Содержит все оставшиеся вершины либо со степенью не более четырех, либо со степенью пять и не более четырех различных смежных вершин (из-за множественных ребер).
• S ₅ : Содержит все оставшиеся вершины, имеющие степень пять, пять различных смежных вершин и по крайней мере одну смежную вершину со степенью не более шести.
• S _d : Содержит все вершины, удаленные из графа на данный момент, в том порядке, в котором они были удалены.

Алгоритм работает следующим образом:

1. На первом этапе мы сворачиваем все кратные ребра в одиночные, так что граф становится простым. Затем мы итерируем по вершинам графа, помещая любую вершину, соответствующую условиям для S ₄ или S ₅ , в соответствующий стек.
2. Далее, пока S ₄ непусто, мы выталкиваем v из S ₄ и удаляем v из графа, помещая его в S _d вместе со списком его соседей на данный момент времени. Мы проверяем каждого бывшего соседа v , ​​помещая его в S ₄ или S ₅ , если он теперь удовлетворяет необходимым условиям.
3. Когда S ₄ становится пустым, мы знаем, что наш граф имеет минимальную степень пять. Если граф пуст, мы переходим к последнему шагу 5 ниже. В противном случае теорема Вернике говорит нам, что S ₅ непусто. Вытащите v из S ₅ , удалите его из графа, и пусть v ₁ , v ₂ , v ₃ , v ₄ , v ₅ будут бывшими соседями v в порядке по часовой стрелке, где v ₁ — сосед степени не более 6. Мы проверяем, является ли v ₁ смежным с v ₃ (что мы можем сделать за постоянное время из-за степени v ₁ ). Есть два случая:
   1. Если v ₁ не является смежной с v ₃ , мы можем объединить эти две вершины в одну вершину. Для этого мы удаляем v из обоих круговых списков смежности, а затем склеиваем два списка в один список в точке, где ранее находился v . При условии, что v сохраняет ссылку на свою позицию в каждом списке, это можно сделать за постоянное время. Возможно, что это может создать грани, ограниченные двумя ребрами в двух точках, где списки склеиваются вместе; мы удаляем одно ребро из любой такой грани. После этого мы помещаем v ₃ на S _d , вместе с примечанием, что v ₁ является вершиной, с которой она была объединена. Любые вершины, затронутые слиянием, добавляются или удаляются из стеков соответствующим образом.
   2. В противном случае v ₂ лежит внутри грани, очерченной v , v ₁ и v ₃ . Следовательно, v ₂ не может быть смежной с v ₄ , которая лежит вне этой грани. Мы объединяем v ₂ и v ₄ таким же образом, как v ₁ и v ₃ выше.
4. Перейти к шагу 2.
5. В этой точке S ₄ , S ₅ и граф пусты. Мы удаляем вершины из S _d . Если вершина была объединена с другой вершиной на шаге 3, вершина, с которой она была объединена, уже будет окрашена, и мы назначаем ей тот же цвет. Это допустимо, поскольку мы объединили только вершины, которые не были смежными в исходном графе. Если бы мы удалили ее на шаге 2, поскольку у нее было не более 4 смежных вершин, все ее соседи на момент удаления уже были бы окрашены, и мы можем просто назначить ей цвет, который не использует ни один из ее соседей.

Альтернативное доказательство

Кайнен (1974) дает упрощенное доказательство теоремы о пяти цветах, основанное на непланарности K ₆ ( полного графа с 6 вершинами) и минорах графа . Это доказательство обобщается на графы, которые можно сделать планарными, удалив 2 ребра. ^[8]

Смотрите также

• Теорема о четырех красках

Ссылки

1. Липтон, Ричард Дж.; Миллер, Рэймонд Э. (1978), «Метод пакетной обработки для раскраски планарных графов», Information Processing Letters , 7 (4): 185–188, doi :10.1016/0020-0190(78)90065-0, MR  0497394
2. Чиба, Норисигэ; Нисидзеки, Такао; Сайто, Нобудзи (1981), «Линейный алгоритм 5-цветной раскраски планарных графов», Журнал алгоритмов , 2 (4): 317–327, doi :10.1016/0196-6774(81)90031-6, MR  0640516
3. Matula, David; Shiloach, Yossi; Tarjan, Robert (ноябрь 1980 г.), Два линейных алгоритма для пятицветной раскраски планарного графа (PDF) , Технический отчет STAN-CS-80-830, Стэнфордский университет
4. Фредериксон, Грег Н. (1984), «О линейных алгоритмах для пятицветной раскраски планарных графов», Information Processing Letters , 19 (5): 219–224, CiteSeerX 10.1.1.158.5812 , doi :10.1016/0020-0190(84)90056-5, MR  0777802 
5. Уильямс, М. Х. (1985), «Линейный алгоритм раскраски планарных графов пятью цветами», The Computer Journal , 28 (1): 78–81, doi : 10.1093/comjnl/28.1.78 , MR  0786929
6. Хагеруп, Торбен; Хробак, Марек; Дикс, Кшиштоф (1989), «Оптимальная параллельная 5-цветная раскраска планарных графов», SIAM Journal on Computing , 18 (2): 288–300, doi :10.1137/0218020, MR  0986668
7. Робертсон, Нил ; Сандерс, Дэниел П.; Сеймур , Пол ; Томас, Робин (1996), «Эффективная раскраска планарных графов четырьмя цветами» (PDF) , Труды 28-го симпозиума ACM по теории вычислений (STOC) , Нью-Йорк: ACM Press.
8. Kainen, Paul C. (сентябрь 1974 г.). "Обобщение теоремы о 5 цветах" (PDF) . Труды Американского математического общества . 45 (3): 450–452. doi :10.2307/2039977. JSTOR  2039977.

Дальнейшее чтение

• Хивуд, П. Дж. (1890), «Теоремы о цвете карт», Quarterly Journal of Mathematics, Оксфорд , т. 24, стр. 332–338