Изменения

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

Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но, как было сказано выше, вызывает до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:  ''"Читатель должен разобраться в <tex>50</tex> страницах текста и диаграмм, <tex>85</tex> страницах с почти <tex>2500</tex> дополнительными диаграммами, <tex>400</tex> страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в <tex>24</tex> леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала <tex>1200</tex> часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно"'' Говоря прямо, компьютерную часть доказательства почти невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Некоторое время назад появилось новое доказательство <ref>Thomas R. An Update on the Four-Color Theorem // Not. Amer. Math. Soc. 1998. Vol. 45, № 7. Р. 848–859.</ref>, причем та часть, которая выполнена не на компьютере, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом веры. == Общие идеи доказательства ==Очевидно, что мы не сможем рассмотреть доказательство целиком, но посмотрим на общие идеи, которые в нем используются.  Во-первыхТеперь, если есть [[Укладка графа на плоскости|гранигрань]] образованные , образованная нашим планарным графом не триангуляция, то есть имеют не ровно три ребра у их границявляющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут триангулированнымитреугольниками. Если эта триангуляция графа полученный граф является раскрашиваемой раскрашиваемым в не более чем <tex>4</tex> и менее цветовцвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему четырех цветов для триангулированных графов, чтобы доказать ее для всех плоских графов, и без потери общности мы предполагаем, что граф триангулирован.

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

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

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