Просмотр исходного текста страницы Проблема четырёх красок

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

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

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

{{Утверждение
|statement=В планарном графе есть вершина степени не больше <tex>4</tex> или конфигурация, состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</tex>
|proof=Зададим функцию <tex>f(v) = 6-deg(v)</tex> и назовем <tex>f(v)</tex> грузом вершины <tex>v</tex>. Предположим что наше утверждение неверно. Следовательно, в графе нет вершин степени не больше <tex>4</tex>. Тогда положительный груз есть только у вершин степени <tex>5</tex> (и он равен единице). У вершин степени <tex>6</tex> груз нулевой, а у всех остальных вершин {{---}} отрицательный. По первому доказанному выше утверждению мы знаем, что <tex>\sum\limits_{v \in V}f(v) = 12 > 0</tex>. Значит вершины степени <tex>5</tex> должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по <tex>\dfrac{1}{5}</tex> своего груза соседям. Тогда у всех вершин степени <tex>5</tex> и <tex>6</tex> груз останется равен <tex>0</tex>, так как вершины степени <tex>5</tex> не смежны с вершинами степени <tex>5</tex> и <tex>6</tex>  по предположению. Рассмотрим все остальные вершины. Поскольку мы проводим доказательство для триангулированных графов, то соседи вершины <tex>v</tex> образуют цикл и на этом цикле <tex>2</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> конфигураций. Для доказательства раскрашиваемости графов с ними был использован компьютер. Из-за сложности этого доказательства, мы не можем рассмотреть его целиком, поэтому более подробно ознакомиться со всеми операциями разгрузки и изучить полученные компьютером раскраски конфигураций можно в двух оригинальных статьях Аппеля и Хакена <ref>[https://projecteuclid.org/download/pdf_1/euclid.ijm/1256049011 Every planar map is four colorable. Part I: Discharging, p. 435]</ref><ref>[https://projecteuclid.org/download/pdf_1/euclid.ijm/1256049012 Every planar map is four colorable. Part II: Reducibility, p. 505]</ref>.

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

== Примeчания ==
<references/>

== Источники информации ==
* [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]

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