Страны
Границы
Использовано цветов
Конфликты

Подробнее о теореме о четырёх красках

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

Какой бы сложной ни была карта, четырёх цветов всегда достаточно, чтобы раскрасить её так, что страны с общей границей никогда не окажутся одного цвета. Утверждение настолько простое, что ребёнок может проверить его цветными карандашами, однако на его доказательство ушло больше века и понадобился компьютер. Раскрасьте случайную карту сами, посмотрите, какие границы конфликтуют, а затем понаблюдайте, как с этим справляются три метода: от быстрого жадного правила, которому иногда нужен пятый цвет, до поиска с возвратом, который всегда обходится четырьмя. Выберите цвет и щёлкайте по странам, чтобы их закрасить; граница становится красной, когда у двух соседей один и тот же цвет. Страны, которые соприкасаются только углом, могут быть одного цвета. Или поручите это компьютеру: выберите метод и нажмите «Решить», чтобы посмотреть, как он работает, или «Шаг», чтобы следить за ним по одному ходу. «Минимум цветов» проверяет, хватит ли этой карте трёх или даже двух цветов. «Новая карта» рисует другую карту, а «Показать соседей» рисует сеть стран, имеющих общую границу.

Как это работает

  1. Выберите количество стран и нажмите «Новая карта» или начните с показанной карты.
  2. Выберите цвет и щёлкайте по странам, чтобы их закрасить, следя за красными границами там, где соседи конфликтуют.
  3. Выберите метод и нажмите «Решить» или «Шаг», чтобы посмотреть, как он раскрашивает карту, а затем нажмите «Минимум цветов», чтобы узнать, сколько цветов нужно этой карте.

От карт к графам

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

Три способа раскраски

Жадная раскраска берёт страны по одной, начиная с тех, у которых больше всего соседей, и даёт каждой первый цвет, ещё не использованный её соседями. Она быстра, но недальновидна и на некоторых картах прибегает к пятому или даже шестому цвету. DSATUR, придуманный Даниэлем Брелазом в 1979 году, всегда выбирает следующей страну, у соседей которой уже больше всего разных цветов, и обычно это позволяет избежать такой ловушки. Поиск с возвратом пробует цвета по очереди и, когда для страны не остаётся ни одного, отменяет последние решения и пробует снова; он всегда находит раскраску в четыре цвета, иногда после многих возвратов.

Часто задаваемые вопросы

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

Короткого объяснения никто не нашёл. Доказательство Кеннета Аппеля и Вольфганга Хакена 1976 года показало, что любая карта обязана содержать одну из 1936 небольших конфигураций и что каждую из них можно удалить, а раскраску затем восстановить; проверка их всех заняла больше тысячи часов компьютерного времени. Более простое компьютерное доказательство Нила Робертсона, Дэниела Сандерса, Пола Сеймура и Робина Томаса 1996 года требует 633 конфигураций, а в 2005 году Жорж Гонтье полностью проверил доказательство с помощью системы интерактивного доказательства Coq.

Нужны ли некоторым картам все четыре цвета?

Да. Четыре страны, каждая из которых касается трёх других, например страна, окружённая кольцом из трёх других, требуют четырёх цветов. Однако многим картам хватает трёх, и «Минимум цветов» выясняет это для карты на экране. Решить в общем случае, можно ли раскрасить карту в три цвета, — трудная, NP-полная задача, хотя четырёх цветов всегда достаточно.

Почему жадный метод иногда использует пять цветов?

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

Верна ли теорема на других поверхностях?

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

Отправляется ли что-нибудь на сервер?

Нет. Карта, методы раскраски и проверка работают в вашем браузере. Ваши настройки остаются в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор