Изменения

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

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

|statement= [[Раскраска_графа#chromatic_number_difinition|Хроматическое число]] планарного графа не превосходит <tex>4</tex>.

Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но как было сказано выше вызывает, до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:  ''"Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно"'' Говоря прямо, компьютерную часть доказательства почти невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Некоторое время назад появилось новое доказательство <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> цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени 5 Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом.}}

На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем Для вершины степени <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> (и он равен единице), у . У вершин степени 6 груз <tex>=06</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>, так как вершины степени 6 <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> конфигураций. Некоторые из них являются сводимымиДля доказательства раскрашиваемости графов с ними был использован компьютер. Из-за сложности этого доказательства, мы не можем рассмотреть его целиком, а другие требуют механической проверки возможности 4-поэтому более подробно ознакомиться со всеми операциями разгрузки и изучить полученные компьютером раскраски. С помощью избавления от сводимых конфигураций можно в двух оригинальных статьях Аппеля и еще ряда эвристик Аппель и Хакен получили 1482 конфигурацииХакена <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>. == См.также ==* [[Раскраска графа]]* [[Хроматическое число планарного графа]] 

* [httphttps://windowwww.eduyoutube.rucom/resource/367/20367/files/0007_091.pdf Проблема 4 красок: неоконченная история доказательстваwatch?v=ysbqis1qofM Лекция Thomas Fernique]