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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 5 участников)
Строка 15: Строка 15:
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
  
В таком виде в <tex>1977</tex> году проблема четырех красок была доказана К. Аппелем и У. Хакеном. Значительную часть проверок выполнил компьютер, из-за чего доказательство было принято не всеми математиками. Доказательство необычайно велико.
+
Теперь, если есть [[Укладка графа на плоскости|грань]], образованная нашим планарным графом, не являющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
 
 
''"Читатель должен разобраться в <tex>50</tex> страницах текста и диаграмм, <tex>85</tex> страницах с почти <tex>2500</tex> дополнительными диаграммами, <tex>400</tex> страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в <tex>24</tex> леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала <tex>1200</tex> часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше."''
 
 
 
Очевидно, что из-за сложности доказательства мы не сможем рассмотреть его целиком, но посмотрим на общие идеи, которые в нем используются.
 
 
 
Во-первых, если [[Укладка графа на плоскости|грани]] образованные нашим планарным графом не триангуляция (то есть имеют не ровно три ребра у их границ), мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут триангулированными. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
 
  
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
Строка 32: Строка 26:
 
Из данного утверждения следует, что в графе существует вершина степени не больше <tex>5</tex>.
 
Из данного утверждения следует, что в графе существует вершина степени не больше <tex>5</tex>.
  
Попытаемся доказать теорему от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф <tex>G</tex>, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым.  
+
Докажем теорему от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф <tex>G</tex>, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым.  
  
 
{{Утверждение
 
{{Утверждение
|statement=В <tex>G~\nexists </tex> <tex>v \in V</tex> : <tex>dev(v) \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> цвета.
 
|proof=Если в <tex>G</tex> есть вершина степени <tex>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>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>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такого набора является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разгрузки].
+
Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф <tex>G</tex> все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такой конфигурации является метод разгрузки<ref>[https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]</ref>.
  
 
Приведем пример нахождения неизбежной конфигурации:
 
Приведем пример нахождения неизбежной конфигурации:
Строка 49: Строка 41:
 
{{Утверждение
 
{{Утверждение
 
|statement=В планарном графе есть вершина степени не больше <tex>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>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>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>.
  
 
== См. также ==
 
== См. также ==

Текущая версия на 19:42, 4 сентября 2022

Теорема (Проблема четырех красок):
Теорема о четырёх красках — утверждение о том, что всякую карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
Карта России раскрашенная в [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чания

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