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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
Строка 11: Строка 11:
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6.</tex>
+
Пусть граф  <tex>G</tex> планарный. Тогда <tex> \chi (G) \le 6.</tex>
 
|proof=
 
|proof=
 
Докажем по индукции.
 
Докажем по индукции.
Строка 25: Строка 25:
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 5.</tex>
+
Пусть граф  <tex>G</tex> планарный. Тогда <tex> \chi (G) \le 5.</tex>
 
|proof=
 
|proof=
 
[[Файл:Planar chromatic number 1.png|230px|thumb|right|u и смежные ей вершины]]
 
[[Файл:Planar chromatic number 1.png|230px|thumb|right|u и смежные ей вершины]]
 
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
 
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
  
Обозначим за <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>.
Строка 43: Строка 43:
 
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
 
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
  
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена.
+
Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся раскраска получена.
  
Если нет, то получили ещё один цикл <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, перекрасить не удаётся ||
+
| || || || ||  Успешное перекрашивание || || || || || || Цикл 1—3, перекрасить не удаётся ||
 
|-
 
|-
| [[Файл:Planar chromatic number 2.png|264px]] || [[Файл:Planar chromatic number 3.png|264px]] || || || || || [[Файл:Planar chromatic number 4.png|228px]] || [[Файл:Planar chromatic number 5.png|228px]]
+
| || || || ||  [[Файл:Planar chromatic number 2.png|264px]] || || || || || || [[Файл:Planar chromatic number 4.png|228px]]
 +
|-
 +
| || || || || [[Файл:Planar chromatic number 3.png|264px]] || || || || || || [[Файл:Planar chromatic number 5.png|228px]]
 
|}
 
|}
  

Версия 11:10, 24 декабря 2015

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

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

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

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

  • База
    Если граф содержит не более 6 вершин, то утверждение очевидно.
  • Переход
    Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в 6 цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.
    По только что доказанной лемме в [math] G [/math] найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.
    Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум 5 цветов). Индукционный переход доказан.
[math]\triangleleft[/math]

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

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

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

Обозначим за [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] в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^{(1)}[/math] в цвет 3. Если среди смежных ей вершин есть вершины [math] v_i^{(3)} [/math], покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:

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

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

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

Если нет, то получили ещё один цикл [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

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

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

Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера. Подробнее см. здесь.

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