Хроматическое число планарного графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 8 участников)
Строка 4: Строка 4:
 
{{Лемма
 
{{Лемма
 
|id=5deg_vertex_lemma  
 
|id=5deg_vertex_lemma  
|statement=В любом графе <tex> G </tex> существует вершина степени не больше 5
+
|statement=В любом планарном графе <tex> G </tex> существует вершина [[Основные определения теории графов#def_undirected_graph_2 | степени]] не больше <tex>5</tex>.
 
|proof=
 
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg} \ u_i \ge 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
+
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg} \; u_i \geqslant 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \geqslant 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \leqslant 3V-6 </tex>. Пришли к противоречию.
 
}}
 
}}
  
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
+
Пусть граф  <tex>G</tex> планарный. Тогда <tex> \chi (G) \leqslant 6.</tex>
 
|proof=
 
|proof=
 
Докажем по индукции.
 
Докажем по индукции.
* База
 
Если граф содержит не более 6 вершин, то утверждение очевидно.
 
* Переход
 
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
 
  
По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.  
+
<u>'''''База индукции'''''</u>
Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
+
 
 +
Если граф содержит не более <tex>6</tex> вершин, то очевидно, что <tex> \chi (G) \leqslant 6.</tex>
 +
 
 +
<u>'''''Индукционный переход'''''</u>
 +
 
 +
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в <tex>6</tex> цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
 +
 
 +
По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше <tex>5</tex>. Удалим её; по предположению индукции получившийся граф можно раскрасить в <tex>6</tex> цветов.  
 +
 
 +
Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум <tex>5</tex> цветов). Индукционный переход доказан.
 
}}
 
}}
  
 
== Раскраска в 5 цветов ==  
 
== Раскраска в 5 цветов ==  
{{Теорема  
+
{{Теорема
 +
|about=
 +
Хивуд
 
|statement=
 
|statement=
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 5</tex>
+
Пусть граф  <tex>G</tex> планарный. Тогда <tex> \chi (G) \leqslant 5.</tex>
 
|proof=
 
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|u и смежные ей вершины]]
+
[[Файл:Planar chromatic number 1.png|230px|thumb|right|<tex>u</tex> и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
+
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с <tex>5</tex>-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
  
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex>  - вершина, покрашенная в <tex> k </tex> цвет.
+
Обозначим за <tex> u </tex> возвращаемую вершину, <tex> v^{(k)} </tex>  — вершину, покрашенную в <tex> k </tex> цвет.
  
 
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим <tex> u </tex>.
 
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим <tex> u </tex>.
  
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.  
+
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость, вернём вершину <tex> u </tex> (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.  
  
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
+
Попробуем покрасить <tex> u </tex> в цвет <tex>1</tex>. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет <tex>3</tex>. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет <tex>1</tex>, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в графе были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
+
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме <tex>1</tex> <tex>\leftrightarrow</tex> <tex>3</tex>, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).  
+
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет <tex>3</tex>, которую перекрасить в <tex>1</tex> нельзя (<tex> u </tex> теперь имеет цвет <tex>1</tex>).  
  
 
Если этот процесс был успешно завершён, то получили правильную раскраску.
 
Если этот процесс был успешно завершён, то получили правильную раскраску.
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в <tex> G </tex> есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
+
Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u </tex>.
  
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена.
+
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет <tex>2</tex>, а смежную ей <tex>w_1^{(2)}</tex> в цвет <tex>4</tex> (со последующими перекрасками). Если удастся раскраска получена.
  
Если нет, то получили ещё один цикл <tex> u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u </tex>. Но граф планарный, значит два полученных цикла пересекаются по крайней мере в двух вершинах - <tex> u </tex> и какой-то другой, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго - разных цветов. Значит такой случай наступить не мог.
+
Если нет, то получили ещё один цикл <tex> u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u </tex>. Но граф планарный, значит два полученных цикла пересекаются помимо вершины <tex> u </tex> по крайней мере ещё в одной, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго разных цветов. Значит такой случай наступить не мог.
  
 
}}
 
}}
  
 
{| cellpadding="10"
 
{| cellpadding="10"
| Успешное перекрашивание ||
+
| || || || ||  Успешное перекрашивание || || || || || || Цикл 1—3, перекрасить не удаётся ||
 +
|-
 +
| || || || ||  [[Файл:Planar chromatic number 2.png|264px]] || || || || || || [[Файл:Planar chromatic number 4.png|228px]] 
 
|-
 
|-
| [[Файл:Planar chromatic number 2.png|280px]] || [[Файл:Planar chromatic number 3.png|280px]]
+
| || || || || [[Файл:Planar chromatic number 3.png|264px]] || || || || || || [[Файл:Planar chromatic number 5.png|228px]]
 
|}
 
|}
  
{| cellpadding="10"
+
Заметим, что не удаётся составить подобное доказательство для раскраски в четыре цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.
| Цикл 1-3, перекрасить не удаётся ||
 
|-
 
| [[Файл:Planar chromatic number 4.png|280px]] || [[Файл:Planar chromatic number 5.png|280px]]
 
|}
 
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
 
  
 
== Раскраска в 4 цвета ==
 
== Раскраска в 4 цвета ==
Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера. Подробнее [http://en.wikipedia.org/wiki/Four_color_theorem см. здесь].
+
{{Теорема
 +
|about=
 +
Проблема четырех красок
 +
|statement='''Теорема о четырёх красках''' — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.
 +
}}
 +
[[Файл:Map of Russia(four colour).png|230px|thumb|right|карта России раскрашенная в <tex>4</tex> цвета]]
 +
Теорема о четырёх красках была доказана в <tex>1976</tex> году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из <tex>1936</tex> карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из <tex>1936</tex> карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих <tex>1936</tex> карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.
 +
 
 +
Чтобы развеять оставшиеся сомнения, в <tex>1997</tex> году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в <tex>2005</tex> году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)
 +
 
 +
== Эквивалентные формулировки ==
 +
В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:
 +
* Хроматическое число планарного графа не превосходит <tex>4</tex>.
 +
* Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета.
 +
 
 +
== Ложное доказательство ==
 +
Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно.
 +
{| cellpadding="0"
 +
| [[Файл:False disproof left.png|230px]] || [[Файл:False disproof right.png|230px]]
 +
|-
 +
 
 +
|}
 +
Карта(слева) окрашена пятью цветами, и нужно изменить как минимум <tex>4</tex> из <tex>10</tex> регионов, чтобы получить окраску в четыре цвета(справа)
  
== Источники ==
+
== Источники информации ==
# http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov
+
* [http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov matica.org {{---}} Раскраска планарного графа ]
# http://ru.wikipedia.org/wiki/Проблема_четырёх_красок
+
* [[wikipedia:ru:Проблема четырёх красок | Википедия {{---}} Проблема четырёх красок]]
 +
* [[wikipedia:en:Four color theorem | Wikipedia {{---}} Four color theorem]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

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

Для планарного графа можно дать оценку сверху на хроматическое число.

Раскраска в 6 цветов

Лемма:
В любом планарном графе [math] G [/math] существует вершина степени не больше [math]5[/math].
Доказательство:
[math]\triangleright[/math]
Предположим это не так. Для любой вершины [math] u_i [/math] графа [math] G [/math] верно [math] \mathrm{deg} \; u_i \geqslant 6 [/math]. Если сложить это неравенство для всех [math] i [/math], получим [math] 2E \geqslant 6V [/math]. Но по следствию из теоремы Эйлера [math] E \leqslant 3V-6 [/math]. Пришли к противоречию.
[math]\triangleleft[/math]
Теорема:
Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 6.[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции.

База индукции

Если граф содержит не более [math]6[/math] вершин, то очевидно, что [math] \chi (G) \leqslant 6.[/math]

Индукционный переход

Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в [math]6[/math] цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.

По только что доказанной лемме в [math] G [/math] найдётся вершина степени не больше [math]5[/math]. Удалим её; по предположению индукции получившийся граф можно раскрасить в [math]6[/math] цветов.

Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум [math]5[/math] цветов). Индукционный переход доказан.
[math]\triangleleft[/math]

Раскраска в 5 цветов

Теорема (Хивуд):
Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 5.[/math]
Доказательство:
[math]\triangleright[/math]
[math]u[/math] и смежные ей вершины

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

Обозначим за [math] u [/math] — возвращаемую вершину, [math] v^{(k)} [/math] — вершину, покрашенную в [math] k [/math] цвет.

Если среди вершин, смежных [math] u [/math], есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим [math] u [/math].

Иначе, уложим полученный после удаления [math] u [/math] граф на плоскость, вернём вершину [math] u [/math] (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.

Попробуем покрасить [math] u [/math] в цвет [math]1[/math]. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^{(1)}[/math] в цвет [math]3[/math]. Если среди смежных ей вершин есть вершины [math] v_i^{(3)} [/math], покрасим их в цвет [math]1[/math], и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:

  1. мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме [math]1[/math] [math]\leftrightarrow[/math] [math]3[/math], и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без [math] u [/math] был раскрашен правильно.
  2. дойдём до вершины, смежной [math] u [/math], исходно имевшей цвет [math]3[/math], которую перекрасить в [math]1[/math] нельзя ([math] u [/math] теперь имеет цвет [math]1[/math]).

Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл [math] u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u [/math].

Тогда попытаемся таким же образом перекрасить [math] u [/math] в цвет [math]2[/math], а смежную ей [math]w_1^{(2)}[/math] в цвет [math]4[/math] (со последующими перекрасками). Если удастся — раскраска получена.

Если нет, то получили ещё один цикл [math] u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u [/math]. Но граф планарный, значит два полученных цикла пересекаются помимо вершины [math] u [/math] по крайней мере ещё в одной, что невозможно, ведь вершины [math] v_i [/math] первого цикла и [math] w_j [/math] второго — разных цветов. Значит такой случай наступить не мог.
[math]\triangleleft[/math]
Успешное перекрашивание Цикл 1—3, перекрасить не удаётся
Planar chromatic number 2.png Planar chromatic number 4.png
Planar chromatic number 3.png Planar chromatic number 5.png

Заметим, что не удаётся составить подобное доказательство для раскраски в четыре цвета, поскольку здесь наличие двух вершин одного цвета среди смежных [math] u [/math] не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.

Раскраска в 4 цвета

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

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

Чтобы развеять оставшиеся сомнения, в [math]1997[/math] году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в [math]2005[/math] году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)

Эквивалентные формулировки

В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:

  • Хроматическое число планарного графа не превосходит [math]4[/math].
  • Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета.

Ложное доказательство

Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно.

False disproof left.png False disproof right.png

Карта(слева) окрашена пятью цветами, и нужно изменить как минимум [math]4[/math] из [math]10[/math] регионов, чтобы получить окраску в четыре цвета(справа)

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