Хроматическое число планарного графа

2016-01-01T18:21:20Z

81.177.127.182: /* Раскраска в 4 цвета */

Для [[Укладка графа на плоскости|планарного графа]] можно дать оценку сверху на [[Раскраска_графа#chromatic_number_difinition|хроматическое число]].

== Раскраска в 6 цветов ==
{{Лемма
|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 \geqslant 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \geqslant 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \leqslant 3V-6 </tex>. Пришли к противоречию.
}}

{{Теорема
|statement=
Пусть граф <tex>G</tex> — планарный. Тогда <tex> \chi (G) \leqslant 6.</tex>
|proof=
Докажем по индукции.

<u>'''''База индукции'''''</u>

Если граф содержит не более <tex>6</tex> вершин, то очевидно, что <tex> \chi (G) \leqslant 6.</tex>

<u>'''''Индукционный переход'''''</u>

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

По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше <tex>5</tex>. Удалим её; по предположению индукции получившийся граф можно раскрасить в <tex>6</tex> цветов.

Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум <tex>5</tex> цветов). Индукционный переход доказан.
}}

== Раскраска в 5 цветов ==
{{Теорема
|about=
Хивуд
|statement=
Пусть граф <tex>G</tex> — планарный. Тогда <tex> \chi (G) \leqslant 5.</tex>
|proof=
[[Файл:Planar chromatic number 1.png|230px|thumb|right|<tex>u</tex> и смежные ей вершины]]
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с <tex>5</tex>-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.

Обозначим за <tex> u </tex> — возвращаемую вершину, <tex> v^{(k)} </tex> — вершину, покрашенную в <tex> k </tex> цвет.

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

Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость, вернём вершину <tex> u </tex> (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.

Попробуем покрасить <tex> u </tex> в цвет <tex>1</tex>. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет <tex>3</tex>. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет <tex>1</tex>, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме <tex>1</tex> <tex>\leftrightarrow</tex> <tex>3</tex>, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет <tex>3</tex>, которую перекрасить в <tex>1</tex> нельзя (<tex> u </tex> теперь имеет цвет <tex>1</tex>).

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

Тогда попытаемся таким же образом перекрасить <tex> u </tex> в цвет <tex>2</tex>, а смежную ей <tex>w_1^{(2)}</tex> в цвет <tex>4</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"
| || || || || Успешное перекрашивание || || || || || || Цикл 1—3, перекрасить не удаётся ||
|-
| || || || || [[Файл:Planar chromatic number 2.png|264px]] || || || || || || [[Файл:Planar chromatic number 4.png|228px]]
|-
| || || || || [[Файл:Planar chromatic number 3.png|264px]] || || || || || || [[Файл:Planar chromatic number 5.png|228px]]
|}

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

== Раскраска в 4 цвета ==
Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера<ref>[http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf microsoft.com {{---}} A computer-checked proof of the Four Colour Theorem] </ref>.

== Примечания ==
<references/>
== Источники информации ==
* [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]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]

Викиконспекты - Вклад участника [ru]

Хроматическое число планарного графа