Хроматическое число планарного графа — различия между версиями
(→Раскраска в 4 цвета) |
(→Ложное доказательство) |
||
Строка 80: | Строка 80: | ||
== Ложное доказательство == | == Ложное доказательство == | ||
Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно. | Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно. | ||
+ | {| cellpadding="0" | ||
+ | | [[Файл:False disproof left.png|230px]] || [[Файл:False disproof right.png|230px]] | ||
+ | |- | ||
+ | |||
+ | |} | ||
+ | Карта(слева) окрашена пятью цветами, и нужно изменить как минимум 4 из 10 регионов, чтобы получить окраску в четыре цвета(справа) | ||
== Эквивалентные формулировки == | == Эквивалентные формулировки == |
Версия 19:25, 29 декабря 2016
Для планарного графа можно дать оценку сверху на хроматическое число.
Содержание
Раскраска в 6 цветов
Лемма: |
В любом планарном графе степени не больше . существует вершина |
Доказательство: |
Предположим это не так. Для любой вершины следствию из теоремы Эйлера . Пришли к противоречию. | графа верно . Если сложить это неравенство для всех , получим . Но по
Теорема: |
Пусть граф — планарный. Тогда |
Доказательство: |
Докажем по индукции. База индукции Если граф содержит не более вершин, то очевидно, чтоИндукционный переход Предположим, что для планарного графа с вершинами существует раскраска в цветов. Докажем то же для графа с вершиной.По только что доказанной лемме в Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум найдётся вершина степени не больше . Удалим её; по предположению индукции получившийся граф можно раскрасить в цветов. цветов). Индукционный переход доказан. |
Раскраска в 5 цветов
Теорема (Хивуд): |
Пусть граф — планарный. Тогда |
Доказательство: |
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с -ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.Обозначим за — возвращаемую вершину, — вершину, покрашенную в цвет.Если среди вершин, смежных , есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим .Иначе, уложим полученный после удаления граф на плоскость, вернём вершину (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.Попробуем покрасить в цвет . Чтобы раскраска осталась правильной, перекрасим смежную ей вершину в цвет . Если среди смежных ей вершин есть вершины , покрасим их в цвет , и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:
Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл .Тогда попытаемся таким же образом перекрасить Если нет, то получили ещё один цикл в цвет , а смежную ей в цвет (со последующими перекрасками). Если удастся — раскраска получена. . Но граф планарный, значит два полученных цикла пересекаются помимо вершины по крайней мере ещё в одной, что невозможно, ведь вершины первого цикла и второго — разных цветов. Значит такой случай наступить не мог. |
Успешное перекрашивание | Цикл 1—3, перекрасить не удаётся | ||||||||||
![]() |
![]() | ||||||||||
![]() |
![]() |
Заметим, что не удаётся составить подобное доказательство для раскраски в четыре цвета, поскольку здесь наличие двух вершин одного цвета среди смежных
не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.Раскраска в 4 цвета
Теорема (Проблема четырех красок): |
Теорема о четырёх красках — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются. |
Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих 1936 карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.
Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)
Ложное доказательство
Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам. Нетрудно доказать, что такую карту начертить нельзя. Можно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно.
![]() |
![]() |
Карта(слева) окрашена пятью цветами, и нужно изменить как минимум 4 из 10 регионов, чтобы получить окраску в четыре цвета(справа)
Эквивалентные формулировки
В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:
- Хроматическое число планарного графа не превосходит 4.
- Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета.