Еще в 1852 году англичанин Фрэнсис Гутри предположил, что любую карту можно раскрасить четырьмя цветами так, чтобы соседние области не сливались. Доказать теорему о четырех красках удалось лишь в 1976 году с помощью громоздких компьютерных расчетов, но из-за невозможности ручной проверки доказательство было принято не всеми. В 1997-м появился упрощенный вариант, тоже компьютерный, и построенный на нем алгоритм раскраски. Однако на больших картах он буксовал: рост числа регионов в десять раз замедлял работу в сто раз.
Спустя почти тридцать лет группа ученых во главе со специалистами Копенгагенского университета совершила прорыв: после десятилетней одержимости «болезнью четырех красок», как в шутку называют эту задачу в научной среде, математики нашли оптимальный алгоритм: теперь при увеличении карты в десять раз время раскраски растет ровно во столько же.
Секрет алгоритма линейной, а не квадратичной сложности кроется в новом взгляде на плоские графы, которыми в математике описывают карты. Ученые обнаружили, что в них гораздо больше приводимых конфигураций, чем считалось: это «зацепки» графа, с которых удобно начать раскраску. Раньше, как правило, удавалось найти лишь одну такую; теперь раскраску можно начинать сразу во многих местах. Более того, как объясняют авторы, обилие «зацепок» позволяет перенести метод с плоских карт на поверхности с отверстиями — вроде надувного круга или куска сыра.