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

Исследование провели ученые из Копенгагенского университета, Технического университета Дании (DTU) и других научных учреждений. Результаты опубликованы на сервере препринтов arXiv. Первая часть работы была представлена на международной конференции по теоретической информатике FOCS 2026 и получила награду за лучшую статью.

Задача о четырех красках возникла в 1852 году, когда английский математик Фрэнсис Гатри заметил, что для раскрашивания карты графств Англии ему хватило четырех цветов. Он предположил, что этого количества достаточно для любой карты, независимо от числа и формы областей, если соседние территории должны различаться по цвету.

Первое доказательство появилось в 1879 году, но спустя 11 лет в нем обнаружили ошибку. Полное доказательство удалось получить лишь в 1976 году. Оно вызвало споры, поскольку в значительной степени опиралось на компьютерные вычисления, которые было трудно независимо проверить. В 1997 году математики предложили более доступное доказательство, однако соответствующий алгоритм работал медленно на больших картах.

Новый алгоритм не меняет саму теорему о четырех красках, а решает другую задачу: позволяет быстрее находить конкретный вариант раскрашивания. По словам профессора Копенгагенского университета Миккеля Торупа, прежние доказательства подтверждали, что раскрашивание четырьмя цветами всегда возможно, но не обеспечивали достаточно эффективного способа определить цвет каждой области.

Ключом к новому результату стало открытие, связанное со структурой графов. В математике карту можно представить в виде планарного графа — системы вершин и соединяющих их линий, расположенных на плоскости без пересечений. Исследователи обнаружили, что такие графы содержат гораздо больше так называемых сводимых конфигураций, чем считалось ранее. Это небольшие участки графа, которые можно использовать как отправные точки для построения раскраски.

«Представьте, что сводимые конфигурации — это ручки, за которые можно ухватиться, чтобы начать раскрашивание четырьмя цветами. Мы показали, что у графов не одна такая ручка, а удивительно много», — объяснил соавтор исследования, профессор DTU Карстен Томассен.

Благодаря этому алгоритм может начинать работу сразу с множества участков графа и обрабатывать большие карты эффективнее. По словам Томассена, сложность вычислений удалось снизить с квадратичной до линейной. Это означает, что если число областей на карте увеличится в десять раз, время вычислений вырастет примерно в десять раз, а не в сто, как при использовании прежнего алгоритма.

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

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