Проблема четырёх красок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Краткая история)
м (Дмитрий Мурзин переименовал страницу Проблема четырех красок в Проблема четырёх красок: Ёфикация)
(не показано 26 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Краткая история ==
 
Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В <tex>1852</tex> году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану, а тот – математической общественности. Точная формулировка гипотезы опубликована А. Кэли в <tex>1878</tex> году. Первое доказательство появилось год спустя и принадлежало В. Кемпе. Одиннадцать лет спустя П. Хивуд обнаружил в нем ошибку (Однако из доказательства Хивуд понял, что пяти красок действительно [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|достаточно]]). За первым ошибочным доказательством последовало множество других. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в <tex>1913</tex> году доказать гипотезу для карты с не более чем <tex>25</tex> странами. Позже это число было увеличено до <tex>38</tex>. В <tex>1977</tex> году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном и опубликовано в двух статьях <ref>Appel K., Haken W. Every Planar Map Is Four Colorable. Contemporary Mathematics. Providence (R.I.): Amer. Math Soc., 1989. Vol. 98. 308 р.</ref>. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день.
 
 
== Формулировка проблемы ==
 
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Строка 9: Строка 5:
 
}}
 
}}
 
[[Файл:Map of Russia(four colour).png|230px|thumb|right|Карта России раскрашенная в <tex>4</tex> цвета]]
 
[[Файл:Map of Russia(four colour).png|230px|thumb|right|Карта России раскрашенная в <tex>4</tex> цвета]]
Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более <tex>20</tex> ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования.
 
  
Поэтому для доказательства начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны (то есть выберем по одной внутренней точке в каждой из стран) и соединим дугами столицы стран, имеющих общий сегмент границы.  В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:
+
== Общие идеи доказательства ==
 +
Начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны и соединим дугами столицы стран, имеющих общий сегмент границы.  В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Строка 19: Строка 15:
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
  
Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но, как было сказано выше, вызывает до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:
+
Теперь, если есть [[Укладка графа на плоскости|грань]], образованная нашим планарным графом, не являющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
 
 
''"Читатель должен разобраться в <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> и менее цветов, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему четырех цветов для триангулированных графов, чтобы доказать ее для всех плоских графов, и без потери общности мы предполагаем, что граф триангулирован.
 
  
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
Строка 37: Строка 24:
 
}}
 
}}
  
Из данного утверждения следует, что в графе существует вершина степени <tex>\leqslant 5</tex>.
+
Из данного утверждения следует, что в графе существует вершина степени не больше <tex>5</tex>.
  
Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leqslant 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета. Следовательно, и таких вершин в искомом графе нет. Для вершины степени <tex>5</tex> Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом.
+
Докажем теорему от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф <tex>G</tex>, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым.  
  
На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело со случаем вершины степени <tex>5</tex>, требуются более сложные операции, чем удаление вершины. Тогда вместо <tex>1</tex> вершины будем рассматривать связанный подграф из нескольких вершин (назовем его '''конфигурацией'''). Тогда для некоторых случаев, как и прежде, достаточно продемонстрировать, что если при удалении конфигурации граф <tex>4</tex>-раскрашиваемый, то окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в <tex>4</tex> цвета. Конфигурации для которых это возможно назовем '''сводимыми'''. Например, конфигурация состоящая из <tex>1</tex> вершины степени <tex>\leqslant 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>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом, используемым, чтобы обнаружить такой набор, является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разрядки]
+
Для вершины степени <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>\leqslant 4</tex> или конфигурация состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</tex>
+
|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>\leqslant 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>, следовательно, сумма грузов отрицательна. Получено противоречие.  
+
|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>4</tex>-раскраски. С помощью избавления от сводимых конфигураций и еще ряда эвристик Аппель и Хакен получили <tex>1482</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чания ==
 
== Примeчания ==
Строка 59: Строка 55:
 
== Источники информации ==
 
== Источники информации ==
 
* [https://www.youtube.com/watch?v=ysbqis1qofM Лекция Thomas Fernique]
 
* [https://www.youtube.com/watch?v=ysbqis1qofM Лекция Thomas Fernique]
* [http://window.edu.ru/resource/367/20367/files/0007_091.pdf Проблема 4 красок: неоконченная история доказательства]
 
 
* [https://en.wikipedia.org/wiki/Four_color_theorem Four color theorem]
 
* [https://en.wikipedia.org/wiki/Four_color_theorem Four color theorem]
 
* [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]
 
* [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]

Версия 23:48, 31 января 2019

Теорема (Проблема четырех красок):
Теорема о четырёх красках — утверждение о том, что всякую карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
Карта России раскрашенная в [math]4[/math] цвета

Общие идеи доказательства

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

Теорема (Хроматическое число планарного графа):
Хроматическое число планарного графа не превосходит [math]4[/math].
4-раскраска планарного графа

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

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

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

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

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

Утверждение:
В [math]G~\nexists [/math] [math]v \in V[/math] : [math]deg(v) \leqslant 4[/math]
[math]\triangleright[/math]
Если в [math]G[/math] есть вершина степени [math]3[/math], то мы можем просто удалить ее из графа, раскрасить полученный граф в [math]4[/math] цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично теореме Хивуда доказывается, что удалив вершину степени [math]4[/math] также всегда можно раскрасить граф в [math]4[/math] цвета.
[math]\triangleleft[/math]

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

Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф [math]G[/math] все равно [math]4[/math]-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такой конфигурации является метод разгрузки[1].

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

Утверждение:
В планарном графе есть вершина степени не больше [math]4[/math] или конфигурация, состоящая из [math]2[/math] вершин степени [math]5[/math] или из вершины степени [math]5[/math] и степени [math]6[/math]
[math]\triangleright[/math]
Зададим функцию [math]f(v) = 6-deg(v)[/math] и назовем [math]f(v)[/math] грузом вершины [math]v[/math]. Предположим что наше утверждение неверно. Следовательно, в графе нет вершин степени не больше [math]4[/math]. Тогда положительный груз есть только у вершин степени [math]5[/math] (и он равен единице). У вершин степени [math]6[/math] груз нулевой, а у всех остальных вершин — отрицательный. По первому доказанному выше утверждению мы знаем, что [math]\sum\limits_{v \in V}f(v) = 12 \gt 0[/math]. Значит вершины степени [math]5[/math] должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по [math]\dfrac{1}{5}[/math] своего груза соседям. Тогда у всех вершин степени [math]5[/math] и [math]6[/math] груз останется равен [math]0[/math], так как вершины степени [math]5[/math] не смежны с вершинами степени [math]5[/math] и [math]6[/math] по предположению. Рассмотрим все остальные вершины. Поскольку мы проводим доказательство для триангулированных графов, то соседи вершины [math]v[/math] образуют цикл и на этом цикле [math]2[/math] вершины степени [math]5[/math] не могут быть рядом. Значит у вершины степени [math]i[/math] не может быть больше чем [math]\bigg\lfloor\dfrac{i}{2}\bigg\rfloor[/math] соседей степени [math]5[/math]. Однако [math](6 - i) + \dfrac{1}{5}\bigg\lfloor\dfrac{i}{2}\bigg\rfloor \lt 0[/math] для [math]i \geqslant 7[/math], следовательно, сумма грузов отрицательна. Получено противоречие.
[math]\triangleleft[/math]

Выше мы получили неизбежную конфигурацию, состоящую из небольшого количество элементов. Подобными действиями К. Аппель и В. Хакен провели [math]487[/math] операций разгрузки и получили неизбежную конфигурацию из [math]1482[/math] конфигураций. Для доказательства раскрашиваемости графов с ними был использован компьютер. Из-за сложности этого доказательства, мы не можем рассмотреть его целиком, поэтому более подробно ознакомиться со всеми операциями разгрузки и изучить полученные компьютером раскраски конфигураций можно в двух оригинальных статьях Аппеля и Хакена [2][3].

См. также

Примeчания

Источники информации