ЧЕТЫРЕ ЦВЕТА ДЛЯ ЛЮБОЙ КАРТЫ — ЗА ЛИНЕЙНОЕ ВРЕМЯ

Любую карту, нарисованную на плоском листе, можно раскрасить четырьмя цветами так, чтобы соседние страны никогда не имели одинакового цвета. Фрэнсис Гутри (Francis Guthrie) высказал эту гипотезу в 1852 году; Аппель и Хакен доказали её в 1976-м. Но теорема говорит лишь о том, что четыре цвета существуют. Как найти их для конкретной карты? «Простого ответа нет», — пишут Юта Иноуэ (Yuta Inoue) из Токийского университета и пятеро его коллег из Японии, Канады, Словении и Дании. Вопрос был настолько запутанным, что породил множество предполагаемых контрпримеров.

Точки, линии и треугольники

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

Перестановка Кемпе

Основной ход восходит к статье А. Б. Кемпе (A. B. Kempe) 1879 года. Разбейте четыре цвета на пары, скажем красный с синим и зелёный с жёлтым. Цепь Кемпе — это связная группа вершин, окрашенных в два цвета одной пары. Перестановка этих двух цветов вдоль всей цепи сохраняет раскраску правильной.

Возьмём вершину v с четырьмя соседями, от v0 до v3 по кругу, и сначала раскрасим всё остальное. Если соседи используют три цвета или меньше, v берёт свободный. Если они используют все четыре, пройдём по цепи, которая начинается в v0 и окрашена в цвета v0 и v2. Если она не доходит до v2, переставим в ней цвета: v0 получит цвет v2, освободив цвет для v. Если же доходит, переставим вместо этого цепь v1 в цветах v1 и v3, так чтобы v1 получила цвет v3.

Куски, которые всегда можно починить

Доказательства теоремы опираются на сводимые конфигурации: небольшие фрагменты, которые можно вырезать, а затем вернуть на место, когда остальное раскрашено. Если цвета их кольца — вершин непосредственно вокруг них — не подходят, ограниченное число улучшающих перестановок Кемпе, сделанных снаружи, всегда это исправляет: не более 25 для используемых здесь фрагментов, кольца которых содержат не более 18 вершин.

Небольшой граф из семи точек, помеченных числами, и тот же граф, окружённый более крупной сеткой треугольников.

Сводимая конфигурация (слева; каждое число — сколько соседей должно быть у этой вершины на полной карте) и тот же фрагмент, дополненный своим кольцом R (справа). — Рисунок 1, Inoue et al. (2026), arXiv:2610.39753.

Робертсон, Сандерс, Сеймур и Томас (Robertson, Sanders, Seymour, Thomas) в 1997 году показали, как раскрашивать таким способом, по одному фрагменту за раз. Каждый раунд уменьшает граф на несколько вершин и стоит прохода по нему целиком, поэтому время квадратичное: для карты вдвое больше — вчетверо дольше.

В предыдущей статье (FOCS’26) те же шестеро авторов доказали, что в каждой триангуляции содержится число несоприкасающихся сводимых конфигураций, пропорциональное n, взятых из списка в 8 202 штуки, — или столько же коротких петель с вершинами по обе стороны, которые тоже помогают. Они удаляют все фрагменты сразу, раскрашивают остальное, а затем чинят все кольца вместе. Случайная перестановка Кемпе помогает данному кольцу, если выбрано правильное разбиение цветов на пары (один шанс из трёх) и правильный бросок монеты на каждой цепи, касающейся кольца (один шанс из двух для каждой). При числе таких цепей до 18 это не меньше одного шанса из 3 × 2¹⁸, то есть из 786 432: мало, но фиксированно. Поэтому число раундов растёт лишь как log n — примерно столько раз, сколько n можно поделить пополам. Но одна перестановка может затронуть постоянную долю графа: каждая стоит полного прохода, всего n log n.

Таблица вместо прохода

Новая статья сохраняет log n перестановок, но делает каждую дешевле. После подготовки, занимающей время, пропорциональное n, каждая перестановка находится и выполняется в среднем примерно за n / log n шагов. Тогда log n перестановок вместе занимают время, пропорциональное n, — линейное время, — и эту оценку авторы называют оптимальной.

Хитрость — «метод четырёх русских». Подзадача, которая умещается в код из ½ log n бит — половину двоичных цифр, нужных для записи n, — имеет не более √n возможных вариантов, так что все их ответы можно вычислить заранее и сохранить в таблице. Предполагаемый компьютер со словами памяти примерно в log n бит считывает любой сохранённый ответ за один шаг.

Граф снова и снова разрезается на вложенные области с короткими границами. Самые маленькие содержат около log n вершин и вместе с цветами умещаются в один код. Для каждой области небольшой сводный граф записывает, какие вершины границы принадлежат одной цепи Кемпе. Перестановка затем спускается вниз в виде строк битов «переставить» или «оставить», и в каждой маленькой области один поиск по таблице обновляет все цвета.

Раскрашенный граф из красных, синих, зелёных и жёлтых точек с обведённой серой областью и несколькими рёбрами, нарисованными жирным чёрным.

Часть графа, раскрашенного четырьмя цветами. Серая зона — область R; жирные чёрные рёбра принадлежат цепям Кемпе для пар красный–синий и зелёный–жёлтый. — Рисунок 2, Inoue et al. (2026), arXiv:2610.39753.

Тот же контур области; её граничные точки соединены тонкими синими линиями с несколькими светло-голубыми пятнами.

Сводка той же области: каждое синее пятно обозначает кусок цепи Кемпе, а его линии показывают, какие вершины границы он соединяет. — Рисунок 3, Inoue et al. (2026), arXiv:2610.39753.

Выбор без игральных костей

Со случайным выбором это уже раскрашивает карту за линейное время в среднем. Убрать кости, не потеряв скорости, было «самой трудной частью, с большим отрывом». Назовём кольцо живым, пока каждое решение до сих пор было в его пользу. Если бы u ещё не решённых цепей, касающихся его, были отданы на волю монеты, оно выжило бы с вероятностью 1/2^u; сумма этих чисел по всем живым кольцам даёт ожидаемое число выживших. Решение по одной цепи удваивает слагаемое каждого кольца, которому был нужен этот выбор, и обнуляет остальные. Алгоритм выбирает вариант, при котором сумма не падает, так что в конце помощь получает не меньше колец, чем в среднем помог бы случай.

Оценка, а не секундомер

Статья не сообщает ни о реализации, ни о времени работы, а константы, скрытые за словами «пропорционально n», не приводятся. Они велики: для каждого из 8 202 фрагментов алгоритм хранит, сколько улучшающих перестановок требуется для каждой раскраски его кольца, — «огромный постоянный объём информации». В приложении авторы также исправляют «небольшую ошибку» в построении вложенных областей 2013 года, на которое они опираются. Гипотеза 1852 года теперь получила процедуру раскраски, затраты которой растут не быстрее, чем карта, которую она раскрашивает.