Редактирование: Проблема четырёх красок

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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=
Строка 5: Строка 9:
 
}}
 
}}
 
[[Файл: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=
Строка 15: Строка 19:
 
[[Файл:Раскраска_планарного_графа_в_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> и менее цветов, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему четырех цветов для триангулированных графов, чтобы доказать это для всех плоских графов, и без потери общности мы предполагаем, что граф триангулирован.
  
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
 
Для дальнейших рассуждений нам понадобится следующее утверждение:
Строка 24: Строка 37:
 
}}
 
}}
  
Из данного утверждения следует, что в графе существует вершина степени не больше <tex>5</tex>.
+
Из данного утверждения следует, что в графе существует вершина степени <tex>\leqslant 5</tex>.
  
Докажем теорему от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф <tex>G</tex>, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым.  
+
Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы 5 цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leqslant 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени <tex>5</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>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>\leqslant 4</tex> является сводимой (было доказано выше). Неизбежными конфигурациями назовем такие множества конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.  
  
Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф <tex>G</tex> все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такой конфигурации является метод разгрузки<ref>[https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) Discharging method]</ref>.
+
Следовательно, нам осталось найти набор всех неизбежных конфигураций и доказать, что с ними граф все равно <tex>4</tex>-раскрашиваем. Основным методом, используемым, чтобы обнаружить такой набор является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разрядки]
  
 
Приведем пример нахождения неизбежной конфигурации:
 
Приведем пример нахождения неизбежной конфигурации:
  
 
{{Утверждение
 
{{Утверждение
|statement=В планарном графе есть вершина степени не больше <tex>4</tex> или конфигурация, состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</tex>
+
|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>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>, следовательно, сумма грузов отрицательна. Получено противоречие.  
+
|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>, следовательно сумма грузов отрицательна. Получено противоречие.  
 
}}
 
}}
  
Выше мы получили неизбежную конфигурацию, состоящую из небольшого количество элементов. Подобными действиями К. Аппель и В. Хакен провели <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>.
+
Подобными операциями Аппелем и Хакеном было получено <tex>487</tex> неизбежных конфигураций. Некоторые из них являются сводимыми, а другие требуют механической проверки возможности 4-раскраски. С помощью избавления от сводимых конфигураций и еще ряда эвристик Аппель и Хакен получили <tex>1482</tex> конфигурации, раскрашиванием которых и занимался компьютер.
 
 
== См. также ==
 
* [[Раскраска графа]]
 
* [[Хроматическое число планарного графа]]
 
 
 
 
== Примeчания ==
 
== Примeчания ==
 
<references/>
 
<references/>
Строка 55: Строка 58:
 
== Источники информации ==
 
== Источники информации ==
 
* [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]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: