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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 5 участников)
Строка 1: Строка 1:
−
== Краткая история ==
 
−
Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В 1852 году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану, а тот – математической общественности. Точная формулировка гипотезы опубликована А. Кэли в 1878 году. Первое доказательство появилось год спустя и принадлежало В. Кемпе. Одиннадцать лет спустя П. Хивуд обнаружил в нем ошибку. (Однако из доказательства Хивуд понял, что пяти красок действительно [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|достаточно]]). За первым ошибочным доказательством последовало множество других. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увеличено до 38. В 1977 году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном и опубликовано в двух статьях <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=
 
Проблема четырех красок
 
Проблема четырех красок
−
|statement='''Теорема о четырёх красках''' — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
+
|statement='''Теорема о четырёх красках''' {{---}} утверждение о том, что всякую карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
 
}}
 
}}
 
[[Файл:Map of Russia(four colour).png|230px|thumb|right|Карта России раскрашенная в <tex>4</tex> цвета]]
 
[[Файл:Map of Russia(four colour).png|230px|thumb|right|Карта России раскрашенная в <tex>4</tex> цвета]]
−
Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более 20 ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования.
 
  
−
Поэтому для доказательства начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны (то есть выберем по одной внутренней точке в каждой из стран) и соединим дугами столицы стран, имеющих общий сегмент границы.  В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:
+
== Общие идеи доказательства ==
 +
Начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны и соединим дугами столицы стран, имеющих общий сегмент границы.  В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
 
Хроматическое число планарного графа
 
Хроматическое число планарного графа
−
|statement= [[Раскраска_графа#chromatic_number_difinition|Хроматическое число]] планарного графа не превосходит 4.
+
|statement= [[Раскраска_графа#chromatic_number_difinition|Хроматическое число]] планарного графа не превосходит <tex>4</tex>.
 
}}
 
}}
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
 
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
  
−
Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но как было сказано выше вызывает, до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:  
+
Теперь, если есть [[Укладка графа на плоскости|грань]], образованная нашим планарным графом, не являющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем <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>-раскрашиваемым.
  
−
Говоря прямо, компьютерную часть доказательства почти невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Некоторое время назад появилось новое доказательство <ref>Thomas R. An Update on the Four-Color Theorem // Not. Amer. Math. Soc. 1998. Vol. 45, № 7. Р. 848–859.</ref>, причем та часть, которая выполнена не на компьютере, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом веры.
+
{{Утверждение
 +
|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>5</tex> аналогичное утверждение неверно, поэтому нельзя просто удалить ее. Тогда вместо <tex>1</tex> вершины будем рассматривать произвольный связный подграф из нескольких вершин (назовем его '''конфигурацией'''). '''Сводимыми''' назовем такие конфигурации, что если при их удалении граф <tex>4</tex>-раскрашиваемый, то его окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в <tex>4</tex> цвета. Например, конфигурация состоящая из <tex>1</tex> вершины степени не больше <tex>4</tex> является сводимой (было доказано выше). '''Неизбежной''' конфигурацией назовем такое '''множество''' конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.  
−
Очевидно, что мы не сможем рассмотреть доказательство целиком, но посмотрим на общие идеи, которые в нем используются.  
 
  
−
Во-первых, если [[Укладка графа на плоскости|грани]] образованные нашим планарным графом не триангуляция, то есть имеют не ровно три ребра у их границ, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут триангулированными. Если эта триангуляция графа является раскрашиваемой в 4 и менее цветов, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему четырех цветов для триангулированных графов, чтобы доказать это для всех плоских графов, и без потери общности мы предполагаем, что граф триангулирован.
+
Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф <tex>G</tex> все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такой конфигурации является метод разгрузки<ref>[https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]</ref>.
  
−
Для дальнейших рассуждений нам понадобится следующее утверждение:
+
Приведем пример нахождения неизбежной конфигурации:
  
 
{{Утверждение
 
{{Утверждение
−
|statement=Для триангулированного графа <tex>\sum\limits^{D}_{i=1}(6-i)v_{i} = 12</tex>, где <tex>v_{i}</tex> {{---}} количество вершин степени <tex>i</tex>, а <tex>D</tex> {{---}} максимальная степень вершины в графе.
+
|statement=В планарном графе есть вершина степени не больше <tex>4</tex> или конфигурация, состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</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>
+
|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> конфигураций. Для доказательства раскрашиваемости графов с ними был использован компьютер. Из-за сложности этого доказательства, мы не можем рассмотреть его целиком, поэтому более подробно ознакомиться со всеми операциями разгрузки и изучить полученные компьютером раскраски конфигураций можно в двух оригинальных статьях Аппеля и Хакена <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чания ==
Строка 41: Строка 54:
  
 
== Источники информации ==
 
== Источники информации ==
−
* [http://window.edu.ru/resource/367/20367/files/0007_091.pdf Проблема 4 красок: неоконченная история доказательства]
+
* [https://www.youtube.com/watch?v=ysbqis1qofM Лекция Thomas Fernique]
 
* [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]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

Текущая версия на 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чания

  1. ↑ Discharging method
  2. ↑ Every planar map is four colorable. Part I: Discharging, p. 435
  3. ↑ Every planar map is four colorable. Part II: Reducibility, p. 505

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Проблема_четырёх_красок&oldid=85880»