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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Раскраска в 6 цветов)
(Раскраска в 6 цветов)
Строка 6: Строка 6:
 
|statement=В любом графе <tex> G </tex> существует вершина [[Основные определения теории графов#def_undirected_graph_2 | степени]] не больше <tex>5</tex>.
 
|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=
 
Докажем по индукции.
 
Докажем по индукции.
Строка 17: Строка 17:
 
'''База индукции'''
 
'''База индукции'''
  
Если граф содержит не более <tex>6</tex> вершин, то очевидно, что <tex> \chi (G) \le 6.</tex>.
+
Если граф содержит не более <tex>6</tex> вершин, то очевидно, что <tex> \chi (G) \leqslant 6.</tex>.
  
 
'''Индукционный переход'''
 
'''Индукционный переход'''

Версия 16:16, 30 декабря 2015

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

Раскраска в 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) \le 5.[/math]
Доказательство:
[math]\triangleright[/math]
u и смежные ей вершины

Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с [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 цвета

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

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