Теорема о четырёх красках: раскраска карты графами

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

Что говорит теорема о четырёх красках

Формально теорема формулируется на языке графов, а не карт. Каждой области карты сопоставляется вершина графа, а две вершины соединяются ребром, если соответствующие области имеют общую границу (не просто общую точку). Такой граф называется планарным - его можно нарисовать на плоскости так, чтобы рёбра не пересекались. Раскраска карты превращается в правильную раскраску вершин: соседние вершины (соединённые ребром) обязаны получить разные цвета, несмежные могут совпадать.

Теорема о четырёх красках утверждает: хроматическое число $\chi(G)$ любого планарного графа $G$ не превышает четырёх, то есть $\chi(G) \le 4$. Она была высказана как гипотеза в 1852 году Фрэнсисом Гутри при попытке раскрасить карту графств Англии, и почти 125 лет оставалась недоказанной, пока в 1976 году Кеннет Аппель и Вольфганг Хакен не завершили доказательство с помощью компьютера.

Рассчитать для своей задачи

Переход от карты к графу - двойственность (dual graph) - ключевой приём: он снимает с задачи геометрию и оставляет только комбинаторику смежности. Именно поэтому теорема формулируется и доказывается для графов, а не для конкретных географических карт.

Почему трёх цветов иногда не хватает

Долгое время казалось, что для карт хватит и трёх цветов, но контрпример находится легко - это граф-колесо $W_n$: центральная вершина (хаб), соединённая со всеми $n$ вершинами внешнего цикла, а сами вершины цикла соединены друг с другом по кругу. Это ровно карта из $n$ областей вокруг одной центральной: все области кольца - соседи по кругу, и все они граничат с центральной.

Хроматическое число цикла $C_n$ известно точно:

$\chi(C_n) = \begin{cases} 2, & n \text{ чётно} \\ 3, & n \text{ нечётно} \end{cases}$

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

$\chi(W_n) = \chi(C_n) + 1 = \begin{cases} 3, & n \text{ чётно} \\ 4, & n \text{ нечётно} \end{cases}$

При чётном $n$ цикл использует всего два цвета, и хабу хватает третьего. А вот при нечётном $n$ цикл уже занял все три доступных цвета - хабу просто не из чего выбирать, нужен четвёртый. Минимальный такой пример - колесо $W_5$ (пять областей вокруг центральной): это классический планарный граф, для которого ровно четыре цвета необходимы и достаточны, три уже не работают.

Рассчитать для своей задачи

На схеме видно, что при трёх цветах внешний пятиугольник раскрашивается корректно (цвета чередуются, последняя вершина получает третий цвет), но хабу деться некуда - все три цвета уже заняты соседями, и он вынужден повторить один из них. Это и есть наглядное доказательство того, что $\chi(W_5) > 3$, то есть ровно $4$.

Жадный алгоритм раскраски по шагам

На практике граф раскрашивают жадным алгоритмом: вершины перебираются в некотором порядке, и каждой присваивается наименьший цвет, не занятый уже раскрашенными соседями. Для графа-колеса порядок имеет значение: если сначала раскрасить весь внешний цикл (используя минимально нужное число цветов), а хаб оставить последним, алгоритм найдёт оптимальную раскраску - ровно $\chi(W_n)$ цветов. Но если начать с хаба и раскрашивать цикл в случайном порядке, жадный алгоритм иногда израсходует лишний цвет там, где можно было обойтись меньшим числом.

Рассчитать для своей задачи

Это общее свойство жадной раскраски: она всегда даёт правильную раскраску (соседи никогда не совпадают), но число использованных цветов зависит от порядка обхода и не всегда равно хроматическому числу. Для произвольных графов задача нахождения именно хроматического числа NP-трудна, поэтому на практике часто довольствуются жадной эвристикой с разумным порядком (например, сначала вершины с наибольшей степенью).

История доказательства: от гипотезы Гутри до Аппеля и Хакена

Гипотезу о четырёх красках сформулировал в 1852 году Фрэнсис Гутри, изучавший студент юриспруденции, заметивший, что графствам Англии на карте хватает четырёх цветов. Он рассказал о наблюдении своему брату Фредерику, который передал вопрос математику Огастесу де Моргану, и с этого момента гипотеза начала циркулировать в математическом сообществе.

Первое опубликованное "доказательство" дал Альфред Кемпе в 1879 году, и десять лет оно считалось верным, пока в 1890 году Перси Хивуд не нашёл в нём ошибку - рассуждение с так называемыми цепями Кемпе работало не во всех случаях. Хивуд, впрочем, спас идею частично: он доказал более слабую теорему о пяти красках, показав, что пяти цветов для любой планарной карты точно достаточно.

Полное доказательство появилось только в 1976 году: Кеннет Аппель и Вольфганг Хакен свели задачу к проверке 1936 (позже сокращённых до 1476) неустранимых конфигураций графа, каждую из которых нужно было проверить отдельно. Вручную это было немыслимо, поэтому проверку доверили компьютеру - суммарно более тысячи часов машинного времени. Это стало первым крупным математическим доказательством, которое невозможно целиком проверить вручную, что вызвало споры о самом статусе такого доказательства: можно ли считать теорему доказанной, если ни один человек не проверил все шаги лично. Со временем доказательство было переработано, независимо перепроверено и формализовано в системе Coq (2005 год), что сняло основные сомнения.

Где раскраска графов работает на практике

Раскраска графов далеко выходит за пределы географических карт. В компиляторах распределение регистров процессора между переменными программы формулируется как раскраска графа конфликтов: переменные - вершины, ребро есть, если две переменные одновременно "живы" и не могут делить один регистр, а число доступных регистров - это верхняя граница числа цветов. Составление расписаний (экзамены, смены, авиарейсы) тоже сводится к раскраске: занятия-вершины, конфликтующие по времени или ресурсу пары соединяются ребром. Более тонкую характеристику того же графа даёт хроматический полином - он не просто отвечает "хватает ли $k$ цветов", а считает, сколькими способами это можно сделать; связанные структурные метрики графа разобраны в статье про радиус и диаметр графа.

Частые ошибки

• Путают карту с графом смежности по вершинам, а не по границам: две области, соприкасающиеся только в одной точке (как штаты, встречающиеся в углу), соседями НЕ считаются - общей должна быть именно граница-отрезок.
• Путают хроматическое число с максимальной степенью вершины. Теорема Брукса ограничивает $\chi(G)$ через максимальную степень для большинства графов, но для планарных графов работает отдельная, более сильная оценка - теорема о четырёх красках.
• Считают, что 4 цвета достаточны для ЛЮБОГО графа. Это верно только для планарных графов; граф $K_5$ (пять вершин, все попарно соединены) непланарен и требует пяти цветов.
• Путают достаточность и необходимость. Теорема гарантирует, что 4 цветов ХВАТИТ, но не значит, что все планарные карты требуют именно 4 - многие раскрашиваются в 2-3 цвета, если в них нет "тяжёлых" конфигураций вроде нечётного колеса.
• Забывают про экватор. Хроматическое число цикла $C_n$ зависит от чётности $n$ - при нечётном числе вершин двух цветов принципиально не хватает, это не ошибка подсчёта, а структурное свойство.

FAQ

Можно ли доказать теорему о четырёх красках без компьютера? Полного доказательства без компьютерного перебора конфигураций пока не существует. Механизм редукции (сведение произвольного контрпримера к одной из ~1476 неустранимых конфигураций) сформулирован математически строго, но проверка самих конфигураций остаётся вычислительно неподъёмной для человека вручную.

Чем теорема о четырёх красках отличается от теоремы о пяти красках? Теорема о пяти красках доказана Хивудом ещё в 1890 году классическими методами без компьютера и покрывает более слабое утверждение (5 цветов вместо 4). Она проще и служит хорошей учебной иллюстрацией техники цепей Кемпе, пусть та же техника и не работает напрямую для случая четырёх цветов.

Работает ли теорема для карт на сфере или торе? Для сферы - да, она эквивалентна плоскому случаю (проекция плоскости на сферу не меняет структуру смежностей). Для тора и других поверхностей с более сложной топологией число цветов растёт: формула Хивуда для рода поверхности $g > 0$ даёт большее число, чем 4 - например, на торе может понадобиться до 7 цветов.

Коротко

Теорема о четырёх красках говорит, что любую карту, а формально - любой планарный граф, можно правильно раскрасить в четыре цвета, не больше. Ключевой приём - перейти от карты к двойственному графу, где области становятся вершинами, а общие границы рёбрами. Три цвета не всегда достаточны: граф-колесо с нечётным числом внешних вершин (например, $W_5$) требует ровно четырёх, потому что нечётный внешний цикл уже занимает три цвета, а центральная вершина граничит со всеми сразу. Доказательство 1976 года Аппеля и Хакена свело задачу к конечному числу неустранимых конфигураций и стало первым крупным математическим результатом, проверенным компьютером, а не вручную. Сама идея раскраски графа при этом живёт далеко за пределами картографии - в распределении регистров компиляторов и составлении расписаний.