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

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

Теорема о пяти цветах вытекает из более сильной теоремы о четырех цветах , но ее значительно легче доказать. Она была основана на неудачной попытке Альфреда Кемпе в 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}$

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

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

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

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

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

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

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

1. На первом этапе мы сворачиваем все несколько ребер в отдельные ребра, чтобы граф был простым. Затем мы перебираем вершины графа, помещая любую вершину, удовлетворяющую условиям для S ₄ или S _5, в соответствующий стек.
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 _{4 так} же, как v ₁ и v ₃ выше.
4. Переходите к шагу 2.
5. В этот момент S ₄ , S ₅ и график пусты. Выделяем вершины из S _d . Если вершина была объединена с другой вершиной на шаге 3, вершина, с которой она была объединена, уже будет окрашена, и мы присваиваем ей такой же цвет. Это верно, потому что мы объединили только те вершины, которые не были смежными в исходном графе. Если бы мы удалили его на шаге 2, потому что у него было не более 4 смежных вершин, все его соседи на момент его удаления уже были бы окрашены, и мы можем просто назначить ему цвет, который не использует ни один из его соседей.

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

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

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

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

• Heawood, PJ (1890), «Теоремы о цвете карты», Quarterly Journal of Mathematics, Oxford , 24 , стр. 332–338. CS1 maint: обескураженный параметр ( ссылка )