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

2018-11-12T20:57:02Z

176.59.21.195: /* Примeчания */

{{Теорема
|about=
Проблема четырех красок
|statement='''Теорема о четырёх красках''' {{---}} утверждение о том, что всякую карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
}}
[[Файл:Map of Russia(four colour).png|230px|thumb|right|Карта России раскрашенная в <tex>4</tex> цвета]]

== Общие идеи доказательства ==
Начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны и соединим дугами столицы стран, имеющих общий сегмент границы. В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:
{{Теорема
|about=
Хроматическое число планарного графа
|statement= [[Раскраска_графа#chromatic_number_difinition|Хроматическое число]] планарного графа не превосходит <tex>4</tex>.
}}
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]

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

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

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

{{Утверждение
|statement=Для триангулированного графа <tex>\sum\limits^{D}_{i=1}(6-i)v_{i} = 12</tex>, где <tex>v_{i}</tex> {{---}} количество вершин степени <tex>i</tex>, а <tex>D</tex> {{---}} максимальная степень вершины в графе.
|proof=Так как граф триангулирован, то <tex>2E=3F</tex>, где <tex>E</tex> {{---}} количество ребер, а <tex>F</tex> {{---}} количество граней. Из [[Формула_Эйлера|формулы Эйлера]] <tex>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</tex>
}}

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

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

{{Утверждение
|statement=В <tex>G~\nexists </tex> <tex>v \in V</tex> : <tex>dev(v) \leqslant 4</tex>
|proof=Если в <tex>G</tex> есть вершина степени <tex>3</tex>, то мы можем просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета.
}}

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

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

Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф <tex>G</tex> все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такого набора является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разгрузки].

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

{{Утверждение
|statement=В планарном графе есть вершина степени не больше <tex>4</tex> или конфигурация, состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</tex>
|proof=Присвоим каждой вершине <tex>v</tex> некую величину {{---}} '''груз''' <tex>=6-deg(v)</tex>. Предположим что наше утверждение неверно. Следовательно, в графе нет вершин степени не больше <tex>4</tex>. Тогда положительный груз есть только у вершин степени <tex>5</tex> (и он равен единице). У вершин степени <tex>6</tex> груз <tex>=0</tex>, а у всех остальных он отрицательный. По первому доказанному выше утверждению мы знаем, что сумма грузов по всем вершинам <tex>=12 > 0</tex>. Значит вершины степени <tex>5</tex> должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по <tex>\dfrac{1}{5}</tex> своего груза соседям. Тогда у всех вершин степени <tex>5</tex> и <tex>6</tex> груз останется равен <tex>0</tex> (помним что вершины степени <tex>6</tex> не смежны с вершинами степени <tex>5</tex> по предположению). Рассмотрим все остальные вершины. Так как мы проводим доказательство для триангулированных графов, то у вершины степени <tex>i</tex> не может быть больше чем <tex>\bigg\lfloor\dfrac{i}{2}\bigg\rfloor</tex> соседей степени <tex>5</tex>. Однако <tex>(6 - i) + \dfrac{1}{5}\bigg\lfloor\dfrac{i}{2}\bigg\rfloor < 0</tex> для <tex>i \geqslant 7</tex>, следовательно, сумма грузов отрицательна. Получено противоречие.
}}

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

== См. также ==
* [[Раскраска графа]]
* [[Хроматическое число планарного графа]]

== Источники информации ==
* [https://www.youtube.com/watch?v=ysbqis1qofM Лекция Thomas Fernique]
* [https://en.wikipedia.org/wiki/Four_color_theorem Four color theorem]
* [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Раскраски графов]]

Викиконспекты - Вклад участника [ru]

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