Раскраска карт: теорема о четырёх красках

Сколько красок нужно, чтобы соседние страны на карте всегда отличались? Ответ — ровно четыре.

Теорема о четырёх красках — любую карту на плоскости можно раскрасить четырьмя цветами так, что никакие две соседние области не будут одного цвета.

Задача родилась в 1852 году, когда студент пытался раскрасить карту графств Англии. Гипотеза, что четырёх красок всегда хватает, продержалась более ста лет и стала первой крупной теоремой, доказанной с помощью компьютера в 1976 году.

Карта как граф

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

# Граф соседства: вершина -> список соседей
graph = {
    0: [1, 2, 3],
    1: [0, 2],
    2: [0, 1, 3],
    3: [0, 2],
}

color = {}
for v in sorted(graph):
    used = {color[u] for u in graph[v] if u in color}
    c = 0
    while c in used:
        c += 1
    color[v] = c

print("Раскраска (вершина: цвет):", color)
print("Использовано цветов:", max(color.values()) + 1)

Вывод:

Раскраска (вершина: цвет): {0: 0, 1: 1, 2: 2, 3: 1}
Использовано цветов: 3

Как работает под капотом

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

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

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

Итог

Любая плоская карта раскрашивается в 4 цвета.
Карта = граф: страны — вершины, соседство — рёбра.
Хроматическое число плоского графа $\le 4$.
Первая теорема, доказанная компьютерным перебором (1976).