Изменения

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

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

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

''"Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текстаДокажем теорему от противного. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времениПусть у нас существует граф, а при проверке вручную потребовалось который требует хотя бы гораздо больше<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_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <reftex>Thomas R. An Update on the Four-Color Theorem 4<// Not. Amer. Math. Soc. 1998. Vol. 45, № 7. Р. 848–859.tex> также всегда можно раскрасить граф в <tex>4</reftex>, причем та часть, которая выполнена не на компьютере, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом верыцвета.}}

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

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

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

|statement=Для триангулированного графа В планарном графе есть вершина степени не больше <tex>\sum\limits^{D}_{i=1}(6-i)v_{i} = 124</tex>или конфигурация, где состоящая из <tex>v_{i}2</tex> {{---}} количество вершин степени <tex>i5</tex> или из вершины степени <tex>5</tex>, а и степени <tex>D6</tex> {{---}} максимальная степень вершины в графе.|proof=Так как граф триангулирован, то Зададим функцию <tex>2Ef(v) =3F6-deg(v)</tex> и назовем <tex>f(v)</tex> грузом вершины <tex>v</tex>. Предположим что наше утверждение неверно. Следовательно, где в графе нет вершин степени не больше <tex>4</tex>. Тогда положительный груз есть только у вершин степени <tex>5</tex> (и он равен единице). У вершин степени <tex>E6</tex> груз нулевой, а у всех остальных вершин {{---}} количество реберотрицательный. По первому доказанному выше утверждению мы знаем, а что <tex>\sum\limits_{v \in V}f(v) = 12 > 0</tex>. Значит вершины степени <tex>F5</tex> {{---}} количество гранейдолжны компенсировать все отрицательные грузы других вершин. Из [[Формула_Эйлера|формулы Эйлера]] Пусть каждая такая вершина отдает по <tex>V - E + \dfrac{21}{35}E = </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>\rightarrow~ 6V - 2E = 6bigg\sumlfloor\limits_dfrac{i=1}^{D2}v_{\bigg\rfloor</tex> соседей степени <tex>5</tex>. Однако <tex>(6 - i} - ) + \sum\limits_dfrac{i=1}^{D5}iv_{i} = \sumbigg\lfloor\limits_dfrac{i=1}^{D2}(6 - \bigg\rfloor < 0</tex> для <tex>i)v_{i} = 12\geqslant 7</tex>, следовательно, сумма грузов отрицательна. Получено противоречие.

Выше мы получили неизбежную конфигурацию, состоящую из небольшого количество элементов. Подобными действиями К. Аппель и В. Хакен провели <tex>487</tex> операций разгрузки и получили неизбежную конфигурацию из <tex>1482</tex> конфигураций. Для доказательства раскрашиваемости графов с ними был использован компьютер. Из данного утверждения следует-за сложности этого доказательства, что мы не можем рассмотреть его целиком, поэтому более подробно ознакомиться со всеми операциями разгрузки и изучить полученные компьютером раскраски конфигураций можно в графе существует вершина степени двух оригинальных статьях Аппеля и Хакена <texref>[https://projecteuclid.org/download/pdf_1/euclid.ijm/1256049011 Every planar map is four colorable. Part I: Discharging, p. 435]</ref><ref>\leq 5[https://projecteuclid.org/download/pdf_1/euclid.ijm/1256049012 Every planar map is four colorable. Part II: Reducibility, p. 505]</texref>.

Вернемся к доказательству нашей теоремы== См. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы 5 цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его 4-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leq 3</tex>, так как иначе мы может просто удалить ее из также ==* [[Раскраска графа, раскрасить полученный граф в 4 цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично ]]* [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме ХивудаХроматическое число планарного графа]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в 4 цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени 5 Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом. На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем вершины степени 5, требуются более сложные операции, чем удаление вершины.

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