40
правок
Изменения
→Раскраска в 4 цвета
{{Лемма
|id=5deg_vertex_lemma
|statement=В любом планарном графе <tex> G </tex> существует вершина [[Основные определения теории графов#def_undirected_graph_2 | степени]] не больше <tex>5</tex>.
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg} \; u_i \ge geqslant 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \ge geqslant 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le leqslant 3V-6 </tex>. Пришли к противоречию.
}}
{{Теорема
|statement=
Пусть граф <tex>G</tex> — планарный. Тогда <tex> \chi (G) \le leqslant 6.</tex>
|proof=
Докажем по индукции.
}}
Хивуд
|statement=
Пусть граф <tex>G</tex> — планарный. Тогда <tex> \chi (G) \le leqslant 5.</tex>
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|<tex>u </tex> и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с <tex>5</tex>-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
== Раскраска в 4 цвета ==
== Источники информации ==
* [http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov matica.org {{---}} Раскраска планарного графа ]
* [[wikipedia:ru:Проблема четырёх красок | Википедия {{---}} Проблема четырёх красок]]
* [[wikipedia:en:Four color theorem | Wikipedia {{---}} Four color theorem]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]