любой планарный граф можно правильно раскрасить в 5 цветов

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

Содержание

Раскраска в 6 цветов [ править ]

Докажем по индукции.

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

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

Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь «занято» максимум [math]5[/math] цветов). Индукционный переход доказан. [math]\triangleleft[/math]

Раскраска в 5 цветов [ править ]

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

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

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

Раскраска в 4 цвета [ править ]

Теорема о четырёх красках была доказана в [math]1976[/math] году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из [math]1936[/math] карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из [math]1936[/math] карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих [math]1936[/math] карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.

Чтобы развеять оставшиеся сомнения, в [math]1997[/math] году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в [math]2005[/math] году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)

Эквивалентные формулировки [ править ]

В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:

Ложное доказательство [ править ]

Карта(слева) окрашена пятью цветами, и нужно изменить как минимум [math]4[/math] из [math]10[/math] регионов, чтобы получить окраску в четыре цвета(справа)

Источник

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

При решении практических задач с применением графов возникает необходимость в разбиении множества вершин графа на классы попарно несмежных между вершин. Довольно часто дополнительно требуется, чтобы таких классов было наименьшее число. В теории графов подобные задачи формулируются в терминах раскраски вершин графа.

В теме рассматриваются только обыкновенные графы.

§1. Хроматическое число

§2. Оценки хроматического числа

§3 Проблема четырех красок

§4. Раскраска пятью красками

Параграф посвящен доказательству утверждения о том, что любой плоский граф можно раскрасить пятью красками (теорема 5.5). Предварительно установим следующий результат.

Теорема 5.4. В любом плоском графе найдется вершина, имеющая степень не выше пяти.

Доказательство. Очевидно, что теорему достаточно доказать для связных плоских графов.

Пусть G – связный плоский граф. Тогда для G справедливо равенство

(теорема Эйлера о многогранниках). Напомним, что r – число граней графа G, т.е. число максимальных связных областей, на которые граф разбивает плоскость. Всякая грань ограничивается, по крайней мере, тремя ребрами, а каждое ребро может входить в границу не более чем двух граней. Следовательно,

Отсюда следует, что

n-m+r £ n-m+2/3m = n-1/3m и n-1/3m ³ 2

Сумма степеней всех вершин равна удвоенному числу ребер, поэтому

m=1/2 r (v).

Подставим это значение m в неравенство n-1/3m ³ 2, получим, что

n-1/6 r (v) ³ 2, или

Последнее неравенство может быть записано следующим образом

(6- r (v)) ³ 12.

Если степень любой вершины v графа G больше пяти, то в левой части последнего неравенства стоит сумма неположительных чисел. Эта сумма не может быть большей или равной 12. Следовательно, найдется хотя бы одна вершина, степень которой не превосходит пяти.

Теорема 5.5. Каждый плоский граф можно правильно раскрасить пятью красками.

Доказательство проведем индукцией по числу вершин графа. Для графа, состоящего из одной вершины утверждение теоремы очевидно. Предположим, что любой плоский граф, содержащий k вершин, можно правильно раскрасить пятью красками. Пусть плоский граф G содержит k+1 вершину.

По теореме 5.4 граф G содержит вершину, степень которой не превосходит пяти. Обозначим эту вершину через v₀. Граф G’=G–v₀ является плоским и содержит k вершин. Используя предположение индукции, правильно раскрасим граф G’ пятью красками. Если для раскраски вершин, смежных с v₀, использовано четыре краски или меньше, то найдется краска для вершины v₀ и в результате получится правильная раскраска графа G.

Предположим, что для раскраски вершин, смежных с v₀, использованы все пять красок. Отсюда следует, что r (v₀)=5. Занумеруем вершины, смежные v₀, по часовой стрелке (см. рис. 5.10).

Пусть вершина v_i раскрашена i–краской. Обозначим через Н₁₃ подграф графа G, порожденный вершинами, раскрашенными первой и третьей красками. Рассмотрим два случая.

Первый случай: вершины v₁ и v₃ лежат в разных компонентах связности графа Н₁₃. Обозначим через K компоненту связности графа Н₁₃, содержащую вершину v₃. Вершины, принадлежащие K, перекрасим следующим образом: вершины, раскрашенные первой краской, покрасим третьей, а вершины, раскрашенные третьей краской, покрасим первой. Мы получим правильную раскраску графа G’.

Действительно, если мы возьмем смежные вершины x и y графа G’ и обе эти вершины не лежат в K, то они будут раскрашены разными красками, поскольку не перекрашивались (см. рис. 5.10). Если одна из вершин, скажем х, принадлежит K, а вторая вершина y не принадлежит K, то х раскрашена (и до и после перекрашивания) первой или третьей красками, а вершина y не может быть раскрашена этими красками, поскольку K – компонента связности графа Н₁₃ и y Ï K. Если же обе вершины х и y принадлежат K, то они до перекрашивания были раскрашены разными красками, а после перекрашивания их краски поменяются, но останутся различными. После перекраски вершина v₃ будет раскрашена в первый цвет. Раскрасим вершину v₀ в третий цвет и мы получим правильную раскраску всего графа G.

Второй случай: вершины v₁ и v₃ лежат в одной компоненте связности графа Н₁₃. Тогда они соединены простой цепью, проходящей через вершины графа Н₁₃. Отметим, что если к этой цепи добавить ребро, соединяющее вершины v₀ и v₁, и ребро, соединяющее вершины v₀ и v₃, то получится цикл графа G, который ограничивает часть плоскости, содержащей вершину v₂ (см. рис. 5.10). Рассмотрим теперь подграф Н₂₄ графа G’, содержащий вершины, раскрашенные второй и четвертой красками. Вершины v₂ и v₄ не могут быть соединены цепью в этом графе.

Действительно, в противном случае ребра этой цепи пересекали бы ребра (v₁,v₃)–цепи графа Н₁₃, расширенной ребрами (v₀,v₁) и (v₀,v₃), что невозможно, поскольку G – плоский граф, или новая цепь проходила бы по вершинам старой цепи, что тоже невозможно, так как эти вершины раскрашены разными красками (см. рис. 5.11).

Обозначим буквой L компоненту связности графа Н₂₄, содержащую вершину v₄. Вершины этой компоненты перекрасим: вторую краску заменим на четвертую, а четвертую – на вторую. В результате, как и в первом случае, получим правильную окраску графа G’. Вершина v₄ будет раскрашена второй краской, как и вершина v₂ (так как v₂ Ï L). Четвертая краска освободится для вершины v₀.

Источник

Любой планарный граф можно правильно раскрасить в 5 цветов

Свойство 1. Любая вершина полного графа с шестью или более вершинами и ребрами двух цветов принадлежит, по меньшей мере, трем ребрам одного цвета.

Свойство 2. В любом полном графе с шестью или более вершинами и ребрами двух цветов найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Свойство 3. Если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде «пятиугольника» с красными сторонами и синими диагоналями.

Свойство 4. В любом полном графе с шестью или более вершинами и ребрами одного из двух цветов всегда найдутся два разных треугольника с одноцветными сторонами. Эти два треугольника могут иметь общую вершину или даже общее ребро.

Если два треугольника имеют общую вершину или ребро, то их называют сцепленными.

Свойство 5. В полном графе с семнадцатью или более вершинами и ребрами трех цветов всегда найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Свойство 6. В полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся два треугольника с одноцветными сторонами, которые не являются сцепленными.

Рассмотрим задачу: при каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета? Нас больше всего интересует вопрос, какие графы можно раскрасить с соблюдением определенных условий, чем вопрос, сколькими способами можно выполнить это раскрашивание.

Для удобства будем предполагать, что все графы не содержат петель. Однако будем допускать существование кратных ребер, так как они не влияют на наши рассуждения.

X ( G ) =2 тогда и только тогда, если G — двудольный граф, отличный от вполне несвязного графа.

Гипотеза о четырех красках

Уже сто с лишним лет математики пытаются доказать гипотезу четырех красок. В этом направлении был достигнут значительный прогресс. В печати появилось сообщение (K.Appel, W.Haken, Every planar map is four colorable, Bull. of Amer. Math. Soc., 82, \No\,5 (sept. 1976)), что гипотезу четырех красок удалось обосновать с использованием ЭВМ.

Сформулируем без доказательства несколько относящихся к этой проблеме результатов:

1. Если гипотеза четырех красок не верна, то любой опровергающий ее пример будет очень сложным. Известно, например, что всякий планарный граф, имеющий менее 52 вершин, 4-раскрашиваем.

2. Любой не содержащий треугольников планарный граф 3-раскрашиваем (теорема Греча).

3. Если попытаться доказать гипотезу четырех красок, то достаточно доказать ее для гамильтоновых планарных графов (довольно неожиданный результат Уитни).

Возникновение гипотезы четырех красок исторически связано с раскрашиванием географических карт. Если имеется карта с изображением нескольких стран, то интересно узнать, сколько понадобится цветов для такой раскраски этих стран, чтобы никакие две соседние страны не были окрашены в один и тот же цвет. Возможно, самая привычная форма гипотезы четырех красок такова: любую карту можно раскрасить с помощью четырех красок.

Чтобы сделать это утверждение точным, надо определить, что означает слово «карта». Поскольку в рассматриваемых нами задачах о раскраске требуется, чтобы страны, расположенные по обе стороны ребра, были разного цвета, придется исключить карты, обладающие мостом. Таким образом, удобно определить карту как связный плоский граф, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер.

Теорема. Карта G является 2-раскрашиваемой тогда и только тогда, если G представляет собой эйлеров граф.

Доказательство. Любую вершину V из G должно окружать четное число граней, так как их можно раскрасить в два цвета. Отсюда следует, что степень каждой вершины четна, и поэтому G — эйлеров граф.

Жордановой кривой, или жордановой дугой, на плоскости называется непрерывная кривая, не имеющая самопересечений; замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.

Нетрудно показать, что раскрашивание определено корректно: берем «цикл», состоящий из двух таких жордановых кривых (то есть замкнутую жорданову кривую), и показываем, что он пересекает четное число ребер графа G (надо использовать индукцию по числу вершин, находящихся внутри цикла, и тот факт, что каждой вершине графа G инцидентно четное число ребер).

Источник