Теорема о четырёх красках простыми словами
В 1852 году молодой математик, раскрашивая карту графств Англии, заметил, что четырёх цветов, похоже, хватает, чтобы соседние графства различались. Верно ли это для любой возможной карты? Вопрос стал одной из самых знаменитых задач математики, породил известное ошибочное доказательство, продержавшееся одиннадцать лет, и был окончательно решён в 1976 году способом, который изменил представление математиков о том, что считать доказательством.
Вопрос
Фрэнсис Гутри, бывший студент Огастеса де Моргана, спросил, можно ли любую карту раскрасить в четыре цвета так, чтобы страны с общей границей получили разные цвета. Два правила делают вопрос точным. Страны должны быть связными, то есть каждая состоит из одного куска, а страны, встречающиеся лишь в одной точке, соседями не считаются. Трёх цветов явно не всегда достаточно: стране, окружённой кольцом из трёх других, которые все касаются друг друга, нужен четвёртый. Вопрос в том, нужен ли когда-нибудь пятый.
Карты как графы
Отметьте точку в каждой стране и проведите линию между двумя точками всякий раз, когда их страны имеют общую границу. Получится граф, и поскольку карта лежит на плоском листе, линии можно провести без пересечений: граф планарен. Раскрасить карту — значит раскрасить вершины этого графа так, чтобы концы каждого ребра различались цветом. Наименьшее подходящее число цветов называется хроматическим числом, и теорема о четырёх красках утверждает, что ни у одного планарного графа хроматическое число не превышает четырёх.
Неудавшееся доказательство Кемпе
В 1879 году барристер и математик Альфред Кемпе опубликовал доказательство. Его остроумная идея, которую теперь называют цепями Кемпе, состоит в том, чтобы поменять местами два цвета вдоль связной цепочки стран и освободить цвет там, где он нужен. Доказательство признавали одиннадцать лет, пока в 1890 году Перси Хивуд не нашёл в нём пробел. Исправление Хивуда доказало более слабый результат: пяти цветов всегда достаточно. Цепи Кемпе уцелели и стали инструментом окончательного доказательства.
Почему с пятью цветами просто
В каждом планарном графе есть вершина не более чем с пятью соседями; это следует из формулы Эйлера, которая ограничивает число рёбер планарного графа с n вершинами значением 3n − 6. Удалите такую вершину, раскрасьте остальную карту тем же рассуждением и верните вершину на место. Если её соседи используют меньше пяти цветов, один свободен. Если они используют все пять, перестановка по цепи Кемпе всегда освобождает один. С четырьмя цветами та же перестановка может не сработать — именно этот пробел Кемпе и упустил.
Компьютерное доказательство
В 1976 году Кеннет Аппель и Вольфганг Хакен из Иллинойсского университета доказали теорему. Они показали, что любая карта содержит хотя бы одну из 1936 конфигураций неизбежного набора и что каждая конфигурация сводима: наименьшая карта, которой нужно пять цветов, не может её содержать. Проверка сводимости заняла на компьютерах больше тысячи часов — слишком много, чтобы проверить вручную. Многим математикам было не по себе от доказательства, которое ни один человек не может прочесть целиком, и началась дискуссия о компьютерных доказательствах.
Более простые доказательства и полная проверка
В 1996 году Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас опубликовали более систематическое доказательство с 633 конфигурациями, по-прежнему проверяемое компьютером, но более простое для проверки. В 2005 году Жорж Гонтье и Бенжамен Вернер формализовали всё доказательство в системе интерактивного доказательства Coq, так что каждый логический шаг проверяет небольшая доверенная программа. Сегодня теорема о четырёх красках — один из самых тщательно проверенных результатов в математике.
Алгоритмы раскраски
Найти раскраску данной карты в четыре цвета на практике быстро, но найти наименьшее число цветов для произвольного графа трудно: решить, хватит ли трёх цветов, — NP-полная задача. К практическим методам относятся жадная раскраска в порядке убывания степени, DSATUR, который следующей раскрашивает самую ограниченную вершину, и поиск с возвратом, который перебирает варианты и отменяет их, заходя в тупик. Раскраска графов помогает составлять расписание экзаменов без накладок, назначать радиочастоты так, чтобы соседние передатчики не мешали друг другу, и распределять регистры в компиляторах.
Попробуйте сами
Откройте раскраску карты в четыре цвета, чтобы создавать карты от 4 до 120 стран, раскрашивать их вручную четырьмя цветами и видеть, как конфликты появляются красным. Пусть жадная раскраска, DSATUR или поиск с возвратом решат карту шаг за шагом, покажите граф соседних стран и проверьте, какое наименьшее число цветов на самом деле нужно карте.
Часто задаваемые вопросы
Помогает ли теорема картографам?
Вряд ли. Настоящие карты обычно раскрашивают большим числом цветов для наглядности, и на них есть океаны, озёра и страны из нескольких частей, которые теорема не охватывает. Её значение математическое: она подтолкнула развитие теории графов и поставила вопрос о том, что считать доказательством.
Что такое цепь Кемпе?
Возьмите два цвета, скажем красный и синий, и страну, окрашенную в красный. Её цепь Кемпе — это множество всех красных и синих стран, до которых можно добраться из неё, переходя только через красных и синих соседей. Если поменять красный и синий во всей цепи, раскраска останется правильной, и может освободиться цвет для страны рядом с цепью.
Почему страны из нескольких частей ломают теорему?
Если страна может состоять из отдельных областей, которые все должны быть одного цвета, граф соседства перестаёт быть планарным, и можно построить карты, которым нужно любое число цветов вплоть до 12 при двух частях на страну, как изучал Хивуд в своей задаче об империях.
Почему программа строит карты из точек?
Каждая страна — это область квадрата, которая ближе к одной случайной точке, чем к любой другой, то есть диаграмма Вороного. Так получаются реалистично выглядящие карты из выпуклых стран, а две страны являются соседями ровно тогда, когда у их областей есть общий участок границы, и приложение вычисляет это точно.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть раскраску карты в четыре цвета