Хроматическое число планарного графа — различия между версиями
(→Раскраска в 6 цветов) |
(→Раскраска в 5 цветов) |
||
Строка 39: | Строка 39: | ||
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода: | Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину <tex>v_1^{(1)}</tex> в цвет 3. Если среди смежных ей вершин есть вершины <tex> v_i^{(3)} </tex>, покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода: | ||
− | #мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 <tex>\leftrightarrow</tex> 3, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно. | + | #мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме <tex>1</tex> <tex>\leftrightarrow</tex> <tex>3</tex>, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без <tex> u </tex> был раскрашен правильно. |
#дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1). | #дойдём до вершины, смежной <tex> u </tex>, исходно имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> теперь имеет цвет 1). | ||
Версия 14:28, 30 декабря 2015
Для планарного графа можно дать оценку сверху на хроматическое число.
Содержание
Раскраска в 6 цветов
Лемма: |
В любом графе степени не больше . существует вершина |
Доказательство: |
Предположим это не так. Для любой вершины следствию из теоремы Эйлера . Пришли к противоречию. | графа верно . Если сложить это неравенство для всех , получим . Но по
Теорема: |
Пусть граф — планарный. Тогда |
Доказательство: |
Докажем по индукции.
|
Раскраска в 5 цветов
Теорема (Хивуд): |
Пусть граф — планарный. Тогда |
Доказательство: |
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной. Обозначим за — возвращаемую вершину, — вершину, покрашенную в цвет.Если среди вершин, смежных , есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим .Иначе, уложим полученный после удаления граф на плоскость, вернём вершину (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.Попробуем покрасить в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину в цвет 3. Если среди смежных ей вершин есть вершины , покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл .Тогда попытаемся таким же образом перекрасить Если нет, то получили ещё один цикл в цвет 2, а смежную ей в цвет 4 (со последующими перекрасками). Если удастся — раскраска получена. . Но граф планарный, значит два полученных цикла пересекаются помимо вершины по крайней мере ещё в одной, что невозможно, ведь вершины первого цикла и второго — разных цветов. Значит такой случай наступить не мог. |
Успешное перекрашивание | Цикл 1—3, перекрасить не удаётся | ||||||||||
![]() |
![]() | ||||||||||
![]() |
![]() |
Заметим, что не удаётся составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных
не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.Раскраска в 4 цвета
Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера. Подробнее см. здесь.