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

Краткая история

Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В [math]1852[/math] году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану, а тот – математической общественности. Точная формулировка гипотезы опубликована А. Кэли в [math]1878[/math] году. Первое доказательство появилось год спустя и принадлежало В. Кемпе. Одиннадцать лет спустя П. Хивуд обнаружил в нем ошибку. (Однако из доказательства Хивуд понял, что пяти красок действительно достаточно). За первым ошибочным доказательством последовало множество других. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в [math]1913[/math] году доказать гипотезу для карты с не более чем [math]25[/math] странами. Позже это число было увеличено до [math]38[/math]. В [math]1977[/math] году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном и опубликовано в двух статьях . Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день.

Формулировка проблемы

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

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

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

Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более [math]20[/math] ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования.

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

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

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

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

Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но как было сказано выше вызывает, до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:

"Читатель должен разобраться в [math]50[/math] страницах текста и диаграмм, [math]85[/math] страницах с почти [math]2500[/math] дополнительными диаграммами, [math]400[/math] страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в [math]24[/math] леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала [math]1200[/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]\leqslant 5[/math].

Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы 5 цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его [math]4[/math]-раскрашиваемым. Тогда в таком графе не может быть вершины степени [math] \leqslant 3[/math], так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в [math]4[/math] цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично теореме Хивуда доказывается, что удалив вершину степени [math]4[/math] также всегда можно раскрасить граф в [math]4[/math] цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени [math]5[/math] Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом.

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

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

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

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

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

[math]\triangleright[/math]

Присвоим каждой вершине [math]v[/math] некую величину — груз [math]=6-deg(v)[/math]. Предположим что наше утверждение неверно. Следовательно в графе нет вершин степени [math]\leqslant 4[/math]. Тогда положительный груз есть только у вершин степени [math]5[/math] (и он равен единице), у вершин степени [math]6[/math] груз [math]=0[/math], а у всех остальных он отрицательный. По доказанному выше утверждению, мы знаем что сумма грузов по всем вершинам [math]=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] неизбежных конфигураций. Некоторые из них являются сводимыми, а другие требуют механической проверки возможности 4-раскраски. С помощью избавления от сводимых конфигураций и еще ряда эвристик Аппель и Хакен получили [math]1482[/math] конфигурации, раскрашиванием которых и занимался компьютер.

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

• Лекция Thomas Fernique
• Проблема 4 красок: неоконченная история доказательства
• Four color theorem
• Discharging method