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

Материал из Викиконспекты
Перейти к: навигация, поиск
(6 цветов)
(5 цветов)
Строка 13: Строка 13:
 
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
 
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
  
Для начала покажем что найдётся вершина, степень которой не больше 5.
+
1.Покажем что найдётся вершина, степень которой не больше 5.
  
 
Предположим это не так. Для любой вершины <tex> u_i </tex> верно <tex> deg </tex> <tex> 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> deg </tex> <tex> u_i \ge 6 </tex>. Если выписать это неравенство для всех <tex> i </tex> и сложить, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
+
2.Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов.
 +
3.Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
 
}}
 
}}
  
 +
== Раскраска в 5 цветов ==
 +
{{Теорема
 +
|statement=
 +
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
 +
|proof=
 +
До шага 3 в индукционном переходе доказательство такое же, как в предыдущей теореме. Покажем что для случая с 5-ю цветами можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
 +
 +
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex>  - вершина, покрашенная в <tex> k </tex> цвет.
 +
 +
Если среди вершин, смежных <tex> u </tex> есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>.
  
 +
Иначе, уложим полученный после шага 2 граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
  
 +
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим вершину цвета 1 в цвет 3. Если среди смежных ей вершин найдётся вершина цвета 3, покрасим её в цвет 1, и так далее. Если этот процесс прекратится, то требуемая раскраска получена. В противном случае мы дойдём до вершины, смежной <tex>  u</tex>, исходно имеющей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> уже перекрашена в цвет 1). Если перекраска не удалась, это означает что есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
  
== Раскраска в 5 цветов ==
+
Таким же образом попытаемся перекрасить <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> не учитываем) - противоречие
 +
}}
  
  
Строка 28: Строка 44:
  
 
== Раскраска в 4 цвета ==
 
== Раскраска в 4 цвета ==
 +
 +
== Источники ==
 +
# http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Раскраски графов]]

Версия 19:27, 24 ноября 2013

Введение

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

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

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

  • База

Если граф содержит не более 6 вершин, то утверждение очевидно.

  • Переход

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

1.Покажем что найдётся вершина, степень которой не больше 5.

Предположим это не так. Для любой вершины [math] u_i [/math] верно [math] deg [/math] [math] u_i \ge 6 [/math]. Если выписать это неравенство для всех [math] i [/math] и сложить, получим [math] 2E \ge 6V [/math]. Но по следствию из теоремы Эйлера [math] E \le 3V-6 [/math]. Пришли к противоречию. 2.Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов.

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

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

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

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

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

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

Иначе, уложим полученный после шага 2 граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.

Попробуем покрасить [math] u [/math] в цвет 1. Чтобы раскраска осталась правильной, перекрасим вершину цвета 1 в цвет 3. Если среди смежных ей вершин найдётся вершина цвета 3, покрасим её в цвет 1, и так далее. Если этот процесс прекратится, то требуемая раскраска получена. В противном случае мы дойдём до вершины, смежной [math] u[/math], исходно имеющей цвет 3, которую перекрасить в 1 нельзя ([math] u [/math] уже перекрашена в цвет 1). Если перекраска не удалась, это означает что есть цикл [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]\triangleleft[/math]



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

Источники

  1. http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov