Проблема четырёх красок

Теорема (Проблема четырех красок):

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

Карта России раскрашенная в [math]4[/math] цвета

Общие идеи доказательства

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

Теорема (Хроматическое число планарного графа):

Хроматическое число планарного графа не превосходит [math]4[/math].

4-раскраска планарного графа

В таком виде в [math]1977[/math] году проблема четырех красок была доказана К. Аппелем и У. Хакеном. Значительную часть проверок выполнил компьютер, из-за чего доказательство было принято не всеми математиками. Само доказательство имеет невероятные размеры, и из-за его сложности мы не сможем рассмотреть его целиком, но посмотрим на общие идеи, которые в нем используются.

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

Для дальнейших рассуждений нам понадобится следующее утверждение:

Утверждение:

Для триангулированного графа [math]\sum\limits^{D}_{i=1}(6-i)v_{i} = 12[/math], где [math]v_{i}[/math] — количество вершин степени [math]i[/math], а [math]D[/math] — максимальная степень вершины в графе.

[math]\triangleright[/math]

Так как граф триангулирован, то [math]2E=3F[/math], где [math]E[/math] — количество ребер, а [math]F[/math] — количество граней. Из формулы Эйлера [math]V - E + \dfrac{2}{3}E = 2 ~\rightarrow~ 6V - 2E = 6\sum\limits_{i=1}^{D}v_{i} - \sum\limits_{i=1}^{D}iv_{i} = \sum\limits_{i=1}^{D}(6 - i)v_{i} = 12[/math]

[math]\triangleleft[/math]

Из данного утверждения следует, что в графе существует вершина степени не больше [math]5[/math].

Попытаемся доказать теорему от противного. Пусть у нас существует граф, который требует хотя бы [math]5[/math] цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф [math]G[/math], что удаление любой вершины из него делает его [math]4[/math]-раскрашиваемым.

Утверждение:

В [math]G~\nexists [/math] [math]v \in V[/math] : [math]dev(v) \leqslant 4[/math]

[math]\triangleright[/math]

Если в [math]G[/math] есть вершина степени [math]3[/math], то мы можем просто удалить ее из графа, раскрасить полученный граф в [math]4[/math] цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично теореме Хивуда доказывается, что удалив вершину степени [math]4[/math] также всегда можно раскрасить граф в [math]4[/math] цвета.

[math]\triangleleft[/math]

Для вершины степени [math]5[/math] аналогичное утверждение неверно, хотя оно и присутствовало в одном из первых ошибочных доказательств.

Имея дело со случаем вершины степени [math]5[/math], нельзя просто удалить ее. Тогда вместо [math]1[/math] вершины будем рассматривать связанный подграф из нескольких вершин (назовем его конфигурацией). Сводимыми назовем такие конфигурации, что если при их удалении граф [math]4[/math]-раскрашиваемый, то его окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в [math]4[/math] цвета. Например, конфигурация состоящая из [math]1[/math] вершины степени не больше [math]4[/math] является сводимой (было доказано выше). Неизбежной конфигурацией назовем такое множество конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.

Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф [math]G[/math] все равно [math]4[/math]-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такого набора является метод разгрузки.

Приведем пример нахождения неизбежной конфигурации:

Утверждение:

В планарном графе есть вершина степени не больше [math]4[/math] или конфигурация, состоящая из [math]2[/math] вершин степени [math]5[/math] или из вершины степени [math]5[/math] и степени [math]6[/math]

[math]\triangleright[/math]

Зададим функцию [math]f(v) = 6-deg(v) ~ \forall v \in V[/math] и назовем [math]f(v)[/math] грузом вершины [math]v[/math]. Предположим что наше утверждение неверно. Следовательно, в графе нет вершин степени не больше [math]4[/math]. Тогда положительный груз есть только у вершин степени [math]5[/math] (и он равен единице). У вершин степени [math]6[/math] груз нулевой, а у всех остальных вершин — отрицательный. По первому доказанному выше утверждению мы знаем, что [math]\sum\limits_{v \in V}f(v) = 12 \gt 0[/math]. Значит вершины степени [math]5[/math] должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по [math]\dfrac{1}{5}[/math] своего груза соседям. Тогда у всех вершин степени [math]5[/math] и [math]6[/math] груз останется равен [math]0[/math] (помним что вершины степени [math]6[/math] не смежны с вершинами степени [math]5[/math] по предположению). Рассмотрим все остальные вершины. Так как мы проводим доказательство для триангулированных графов, то у вершины степени [math]i[/math] не может быть больше чем [math]\bigg\lfloor\dfrac{i}{2}\bigg\rfloor[/math] соседей степени [math]5[/math]. Однако [math](6 - i) + \dfrac{1}{5}\bigg\lfloor\dfrac{i}{2}\bigg\rfloor \lt 0[/math] для [math]i \geqslant 7[/math], следовательно, сумма грузов отрицательна. Получено противоречие.

[math]\triangleleft[/math]

Выше мы получили неизбежную конфигурацию, состоящую из небольшого количество элементов. Подобными действиями Аппель и Хакен провели [math]487[/math] операций разгрузки и получили неизбежную конфигурацию из [math]1482[/math] конфигураций. Некоторые из них являются сводимыми, доказательством раскрашиваемости графов с остальными и занимался компьютер.

См. также

• Раскраска графа
• Хроматическое число планарного графа

Источники информации

• Лекция Thomas Fernique
• Four color theorem
• Discharging method