Теорема о четырёх красках: почему любой карте хватит четырёх цветов
Возьми любую карту мира, любую — хоть выдуманную, хоть с тысячей государств. Чтобы соседние страны не сливались по цвету, тебе всегда хватит ровно четырёх красок. Не пяти, не десяти. Звучит как фокус, но это доказанная теорема.
Возьми атлас, цветные карандаши и попробуй раскрасить карту так, чтобы соседние страны не сливались. Сколько цветов уйдёт? Оказывается, чего бы ты ни рисовал — хоть реальную Европу, хоть карту выдуманной планеты с тысячей королевств — четырёх цветов всегда достаточно. Это не наблюдение, а строго доказанная математическая теорема. И история у неё детективная.
С чего всё началось: студент и карта Англии
В 1852 году молодой англичанин Фрэнсис Гатри раскрашивал карту графств Англии и заметил странную вещь: ему хватило всего четырёх цветов, чтобы никакие два соседних графства не оказались одного оттенка. Он попробовал ещё, и ещё — и не смог придумать карту, для которой понадобился бы пятый цвет.
Гатри рассказал об этом брату, тот — своему преподавателю, и так вопрос пошёл гулять по математикам. Сформулировать его легко даже первокласснику: правда ли, что любую карту на плоскости можно раскрасить в четыре цвета так, чтобы соседи отличались? А вот доказать это оказалось чудовищно тяжело. Загадка продержалась больше ста лет.
Сразу договоримся о правилах игры. «Соседи» — это страны, у которых есть общая граница-линия, а не просто общая точка. Иначе на карте, нарезанной как пирог, в одной точке сходилось бы сколько угодно кусков, и никаких четырёх цветов не хватило бы. А ещё каждая страна должна быть единым куском — без заморских колоний-островков.
Почему трёх мало, а четырёх как будто всегда хватает
Сначала убедимся, что три цвета — это слишком мало. Нарисуй четыре страны так, чтобы каждая граничила с каждой: например, одну страну в центре, а вокруг неё — три, как лепестки, и все три тоже касаются друг друга. Получится, что все четыре попарно соседи. Раскрасить их в три цвета невозможно: четвёртой стране просто не останется свободного цвета. Значит, минимум иногда нужно именно четыре.
А дальше начинается самое интересное. Сколько математики ни старались, им не удавалось построить карту, которой нужно пять. Но «не удалось придумать контрпример» — это ещё не доказательство. Карт-то бесконечно много! Может, где-то в этой бесконечности притаился монстр, требующий пятого цвета. Чтобы закрыть вопрос, нужно было железно показать: такого монстра не существует в принципе.
Главная ловушка теоремы в том, что проверить её на тысяче карт легко — а доказать для всех сразу почти невозможно. Бесконечность не объедешь перебором.
Хитрость математиков: превратить карту в точки и линии
Чтобы приручить задачу, математики сделали ловкий ход — выбросили всю лишнюю географию. Какая разница, какой формы страна и сколько у неё километров побережья? Важно только одно: кто с кем граничит.
Поэтому каждую страну заменили на точку, а каждую общую границу — на линию между точками. Получилась схема из точек и соединений, которую называют графом. И теперь вопрос звучит уже не про карты, а про графы: можно ли раскрасить точки в четыре цвета так, чтобы соединённые линией точки были разными?
Это как схема метро. Тебе ведь неважно, сколько реальных метров между станциями и в какую сторону изгибается тоннель — важно лишь, какая станция с какой соединена. Граф — это и есть «карта связей», очищенная от всего лишнего. А ещё карты на плоскости дают особые, планарные графы: их можно нарисовать так, чтобы линии нигде не пересекались. Именно это свойство и держит число цветов под контролем.
Доказательство, которое не уместилось в голове
Прорыв случился в 1976 году. Математики Кеннет Аппель и Вольфганг Хакен придумали стратегию: они показали, что любая мыслимая карта обязательно содержит один из конечного набора «типовых кусочков». Таких неизбежных конфигураций набралось около полутора тысяч. Если каждую из них можно аккуратно вписать в четыре цвета, то и вся карта раскрасится.
Вот только проверить полторы тысячи громоздких случаев вручную человек не в силах — это годы безошибочной работы. Поэтому Аппель и Хакен впервые в истории поручили проверку компьютеру. Машина перебрала все варианты и подтвердила: пятый цвет не нужен никогда. Так теорема о четырёх красках стала первой крупной теоремой, доказанной с помощью компьютера.
И тут вспыхнул спор, который не утих до сих пор. Часть математиков возмутилась: можно ли верить доказательству, которое ни один человек не способен прочитать целиком и проверить своими глазами? Привычное доказательство — это рассуждение, за которым ты следишь шаг за шагом. А здесь приходится доверять программе. Позже доказательство упростили и перепроверили другими, независимыми программами — результат тот же. Четырёх цветов хватает.
Зачем это всё, кроме карандашей
Может показаться, что теорема — забава для картографов. Но идея «раскрась так, чтобы соседи не конфликтовали» работает повсюду, где есть ограничения и связи.
- Расписание экзаменов. Сделай каждый предмет точкой, соедини линией те, что нельзя ставить в один день (их сдаёт один и тот же класс). «Цвет» — это день. Раскраска графа подскажет, как развести экзамены без накладок.
- Частоты вышек связи. Соседним вышкам нельзя вещать на одной частоте, иначе они забьют друг друга. Это снова раскраска: вышки — точки, частоты — цвета.
- Распределение ресурсов в программах. Компиляторы решают похожую задачу, раскладывая переменные по ячейкам памяти процессора.
Так маленькая загадка про карандаши и карту Англии выросла в целую область — теорию графов, без которой не работали бы ни навигаторы, ни расписания, ни мобильная связь. А началось всё с простого детского вопроса: сколько же цветов нужно на самом деле? Ответ — четыре. Всегда четыре.