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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Хроматический многочлен планарного графа»)
 
(6 цветов)
Строка 1: Строка 1:
Хроматический многочлен планарного графа
+
== Введение ==
 +
 
 +
 
 +
== Раскраска в 6 цветов ==
 +
{{Теорема
 +
|statement=
 +
Пусть граф  <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
 +
|proof=
 +
Докажем по индукции.
 +
* База
 +
Если граф содержит не более 6 вершин, то утверждение очевидно.
 +
* Переход
 +
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
 +
 
 +
Для начала покажем что найдётся вершина, степень которой не больше 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>. Пришли к противоречию.
 +
Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
 +
}}
 +
 
 +
 
 +
 
 +
 
 +
== Раскраска в 5 цветов ==
 +
 
 +
 
 +
 
 +
 
 +
== Раскраска в 4 цвета ==

Версия 18:50, 24 ноября 2013

Введение

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

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

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

  • База

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

  • Переход

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

Для начала покажем что найдётся вершина, степень которой не больше 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]. Пришли к противоречию.

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



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

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