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

Для планарного графа можно дать оценку сверху на хроматическое число.

Раскраска в 6 цветов

Лемма:

В любом планарном графе [math] G [/math] существует вершина степени не больше [math]5[/math].

Доказательство:

[math]\triangleright[/math]

Предположим это не так. Для любой вершины [math] u_i [/math] графа [math] G [/math] верно [math] \mathrm{deg} \; u_i \geqslant 6 [/math]. Если сложить это неравенство для всех [math] i [/math], получим [math] 2E \geqslant 6V [/math]. Но по следствию из теоремы Эйлера [math] E \leqslant 3V-6 [/math]. Пришли к противоречию.

[math]\triangleleft[/math]

Теорема:

Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 6.[/math]

Доказательство:

[math]\triangleright[/math]

Докажем по индукции. База индукции Если граф содержит не более [math]6[/math] вершин, то очевидно, что [math] \chi (G) \leqslant 6.[/math] Индукционный переход Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в [math]6[/math] цветов. Докажем то же для графа с [math] N+1 [/math] вершиной. По только что доказанной лемме в [math] G [/math] найдётся вершина степени не больше [math]5[/math]. Удалим её; по предположению индукции получившийся граф можно раскрасить в [math]6[/math] цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум [math]5[/math] цветов). Индукционный переход доказан.

[math]\triangleleft[/math]

Раскраска в 5 цветов

Теорема (Хивуд):

Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 5.[/math]

Доказательство:

[math]\triangleright[/math]

[math]u[/math] и смежные ей вершины Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с [math]5[/math]-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной. Обозначим за [math] u [/math] — возвращаемую вершину, [math] v^{(k)} [/math] — вершину, покрашенную в [math] k [/math] цвет. Если среди вершин, смежных [math] u [/math], есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим [math] u [/math]. Иначе, уложим полученный после удаления [math] u [/math] граф на плоскость, вернём вершину [math] u [/math] (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке. Попробуем покрасить [math] u [/math] в цвет [math]1[/math]. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^{(1)}[/math] в цвет [math]3[/math]. Если среди смежных ей вершин есть вершины [math] v_i^{(3)} [/math], покрасим их в цвет [math]1[/math], и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода: мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме [math]1[/math] [math]\leftrightarrow[/math] [math]3[/math], и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без [math] u [/math] был раскрашен правильно. дойдём до вершины, смежной [math] u [/math], исходно имевшей цвет [math]3[/math], которую перекрасить в [math]1[/math] нельзя ([math] u [/math] теперь имеет цвет [math]1[/math]). Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл [math] u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u [/math]. Тогда попытаемся таким же образом перекрасить [math] u [/math] в цвет [math]2[/math], а смежную ей [math]w_1^{(2)}[/math] в цвет [math]4[/math] (со последующими перекрасками). Если удастся — раскраска получена. Если нет, то получили ещё один цикл [math] u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u [/math]. Но граф планарный, значит два полученных цикла пересекаются помимо вершины [math] u [/math] по крайней мере ещё в одной, что невозможно, ведь вершины [math] v_i [/math] первого цикла и [math] w_j [/math] второго — разных цветов. Значит такой случай наступить не мог.

[math]\triangleleft[/math]

				Успешное перекрашивание						Цикл 1—3, перекрасить не удаётся

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

Раскраска в 4 цвета

Теорема (Проблема четырех красок):

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

карта России раскрашенная в [math]4[/math] цвета

Теорема о четырёх красках была доказана в [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]4[/math] из [math]10[/math] регионов, чтобы получить окраску в четыре цвета(справа)

Источники информации

• matica.org — Раскраска планарного графа
• Википедия — Проблема четырёх красок
• Wikipedia — Four color theorem