Теорема пяти цветов - Five color theorem

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

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

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

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

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

Теперь удалите ${\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}$ в циклическом порядке (который зависит от того, как мы пишем G). Если бы мы не использовали на них все пять цветов, то очевидно, что мы можем раскрасить ${\displaystyle v}$ последовательным образом, чтобы наш график был 5-цветным.

Итак, мы можем предположить, что ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$, ${\displaystyle v_{4}}$, ${\displaystyle v_{5}}$ окрашены в цвета 1, 2, 3, 4, 5 соответственно.

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

Если наоборот ${\displaystyle v_{1}}$ и ${\displaystyle v_{3}}$ лежат в одной связной компоненте ${\displaystyle G_{1,3}}$, мы можем найти путь в ${\displaystyle G_{1,3}}$ соединяющий их, состоящий только из вершин цвета 1 и 3.

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

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

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

В 1996 году Робертсон, Сандерс, Сеймур и Томас описали квадратичный алгоритм четырехкратной раскраски в своих «Планарных графах с эффективной четырехкратной раскраской».^[1] В той же статье они кратко описывают алгоритм пятикратной раскраски с линейным временем, который асимптотически оптимальный. Описанный здесь алгоритм работает с мультиграфами и полагается на возможность иметь несколько копий ребер между одной парой вершин. Он основан на Теорема Вернике, в котором говорится следующее:

Теорема Вернике: Предполагать грамм плоский, непустой, не имеет граней, ограниченных двумя ребрами, и имеет минимум степень 5. Затем грамм имеет вершину степени 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 смежных вершин, все его соседи на момент его удаления уже были бы окрашены, и мы можем просто назначить ему цвет, который не использует ни один из его соседей.

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

• Теорема четырех цветов

Рекомендации

1. Робертсон, Нил; Сандерс, Дэниел П.; Сеймур, Пол; Томас, Робин (1996), «Эффективно четырехцветные плоские графы» (PDF), Proc. 28-й симпозиум ACM по теории вычислений (STOC), Нью-Йорк: ACM Press..

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

• Хивуд, П. Дж. (1890), "Теоремы о цвете карты", Ежеквартальный журнал математики, Оксфорд, 24, стр. 332–338