308
правок
Изменения
Новая страница: «Для планарного графа можно дать оценку сверху на [[Раскраска_графа#chromatic_number_difinition|хромат...»
Для планарного графа можно дать оценку сверху на [[Раскраска_графа#chromatic_number_difinition|хроматическое число]].
== Раскраска в 6 цветов ==
{{Лемма
|id=5deg_vertex_lemma
|statement=В любом графе <tex> G </tex> существует вершина степени не больше 5
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </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>. Пришли к противоречию.
}}
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
|proof=
Докажем по индукции.
* База
Если граф содержит не более 6 вершин, то утверждение очевидно.
* Переход
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.
Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
}}
== Раскраска в 5 цветов ==
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 5</tex>
|proof=
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершина, покрашенная в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>.
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим 2 необычных варианта, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и если мы получили две смежные вершины одного цвета, значит и до перекрасок в графе были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).
Если этот процесс был успешно завершён, то получили правильную раскраску.
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в <tex> G </tex> есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
Тогда попытаемся таким же образом перекрасить <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> и какой-то другой, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго - разных цветов. В этом случае получаем противоречие.
}}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
== Раскраска в 4 цвета ==
== Источники ==
# http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
== Раскраска в 6 цветов ==
{{Лемма
|id=5deg_vertex_lemma
|statement=В любом графе <tex> G </tex> существует вершина степени не больше 5
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </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>. Пришли к противоречию.
}}
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
|proof=
Докажем по индукции.
* База
Если граф содержит не более 6 вершин, то утверждение очевидно.
* Переход
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.
Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
}}
== Раскраска в 5 цветов ==
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 5</tex>
|proof=
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершина, покрашенная в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся один свободный цвет, в который мы и покрасим <tex> u </tex>.
Иначе, уложим полученный после удаления <tex> u </tex> граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_2^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим 2 необычных варианта, которые могут наступить во время обхода:
#мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и если мы получили две смежные вершины одного цвета, значит и до перекрасок в графе были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно.
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1).
Если этот процесс был успешно завершён, то получили правильную раскраску.
Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в <tex> G </tex> есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
Тогда попытаемся таким же образом перекрасить <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> и какой-то другой, что невозможно, ведь вершины <tex> v_i </tex> первого цикла и <tex> w_j </tex> второго - разных цветов. В этом случае получаем противоречие.
}}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
== Раскраска в 4 цвета ==
== Источники ==
# http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
