# Торуп и Томассен представили на FOCS алгоритм раскраски карт в четыре цвета за линейное время

- Опубликовано: 2026-11-19 13:31 UTC
- Раздел: Цифра и вычисления › Софт и сервисы
- Теги: теорема четырёх цветов, алгоритм раскраски карт, линейное время, планарные графы, редуцируемые конфигурации, Миккель Торуп, Карстен Томассен, конференция FOCS, раскраска графов
- Адрес: https://realtech.media/ru/news/rt-8c0fc8c5a5a98fde9dbb9741_torup_i_tomassen/

**Новый алгоритм раскраски плоских карт в четыре цвета работает за линейное, а не квадратичное время: карта в 10 раз больше требует в 10 раз больше расчётов, а не в 100.**

![Thorup, Thomassen and colleagues present a linear-time four-colouring algorithm for planar maps at FOCS](https://realtech.media/media/2026/11/dbe7fd78e46ccb42.jpg)
*pravda.ru*

Международная группа исследователей, включая Миккеля Торупа из Копенгагенского университета и Карстена Томассена из Технического университета Дании, представила на конференции Foundations of Computer Science (FOCS) новый алгоритм раскраски плоских карт в четыре цвета, сообщает pravda.ru [1]. Время его работы растёт линейно с размером карты, тогда как прежние алгоритмы масштабировались квадратично [1]. Это не новое доказательство теоремы четырёх цветов, а поиск оптимального способа её реализации [1].

## Теорема и проблема скорости

Тезис о том, что для любой плоской карты достаточно четырёх цветов, сформулировал Фрэнсис Гатри в 1852 году [1]. Первое доказательство, найденное в 1879 году, оказалось ошибочным, а окончательный ответ получили только в 1976 году с помощью компьютерной программы [1]. Теорема считается решённой, но существовал разрыв между знанием того, что раскраска возможна, и наличием быстрого способа её построить [1].

У прежних алгоритмов время вычислений росло квадратично. Если число регионов увеличивалось в 10 раз, расчёт занимал в 100 раз больше времени, что осложняло работу с большими массивами данных [1].

## Редуцируемые конфигурации как отправные точки

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

Главный результат команды в том, что таких «ручек» в графах гораздо больше, чем считалось ранее [1]. Вместо последовательной раскраски алгоритм находит множество таких точек одновременно и заполняет области параллельно [1]. Это переводит сложность вычислений из квадратичной в линейную: карта в 10 раз больше замедляет расчёт в 10 раз, а не в 100 [1].

Исследователи отмечают, что подход работает и для поверхностей с отверстиями, например для объектов по форме вроде тора или куска сыра с дырками [1]. Торуп иронично называет задачу «болезнью четырёх цветов» [1]. По сообщению издания, решение даёт новые инструменты для других сложных математических задач, где нужен быстрый перебор вариантов и поиск оптимальных структур [1].

## Источники

1. [pravda.ru](https://www.pravda.ru/news/science/2445797-mathematicians-make)

---

Источник: RealTech, realtech.media — https://realtech.media/ru/news/rt-8c0fc8c5a5a98fde9dbb9741_torup_i_tomassen/
