Теорема четырёх красок: как математика и компьютер решили задачу о раскраске карт

Сколько цветов нужно, чтобы раскрасить карту так, чтобы соседние страны были разных цветов?

Интуитивно кажется — много. Но, оказывается, достаточно всего четырех. А сама задача стала первой на стыке математики и, как бы сейчас сказали, AI.

Для начала договоримся про понятия. Соседние страны — значит имеют общую границу ненулевой длины, а если страны соприкасаются только в одной точке, то им можно быть одного цвета. Допустим ещё, что у стран нет «анклавов», то есть каждая — одна связная область.

История задачи о раскраске карт: как родилась теорема четырёх красок

📚 Всё началось ещё в 1852 году. Фрэнсис Гатри раскрашивал карту Англии и заметил закономерность. Через брата он передал вопрос профессору Августу де Моргану. Задача ушла в мир математики, но решение не удавалось найти более 100 лет!

Доказательство теоремы четырёх красок: на помощь приходит компьютер

✨ Только в 1976 году Аппель и Хакен с помощью компьютера перебрали все возможные варианты определенных комбинаций и доказали, что 4х красок достаточно.

В первые в истории компьютер помог найти решение задачи, которую человек решить был не в состоянии. Математики, конечно, приняли решение прохладно. Доказательство перепроверяли и упрощали, a в итоге оно стало классикой подхода к решению задач с помощью AI.

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

🧠 Задачу легко перевести на язык графов: заменяем каждую страну на вершину, а общую границу — на ребро. Тогда вопрос становится таким: сколько цветов нужно, чтобы раскрасить вершины планарного графа, чтобы у каждого ребра концы были разного цвета?

Теорема четырёх красок на других поверхностях

🔷 Важная тонкость: речь именно о плоскости (или сфере, что по сути то же самое). На других поверхностях правила меняются: например, для карты на торе уже нужно 7 цветов, а на ленте Мёбиуса — 6.

Про задачу рассказывал здесь.