Найдено эффективное решение к 174-летней математической головоломке

Ученые усилили доказательство теоремы о четырех красках — первой крупной математической теоремы, доказанной с использованием компьютера — и обошлись при этом без помощи искусственного интеллекта. Новый, более эффективный алгоритм решения 174-летней головоломки описан на arXiv. Статья получила награду на одной из ведущих мировых конференций по теоретической информатике FOCS'26.
В 1852 году математик Фрэнсис Гутри, составляя карту графств Англии, обратил внимание, что для этой цели хватает четырех красок. Он предположил, что карту любого размера и сложности можно раскрасить всего четырьмя цветами так, чтобы никакие две соседние области не были одного цвета.
С подачи брата Гутри теорема вызвала живейший интерес в математическом сообществе. В 1879 году было представлено первое доказательство, но спустя 11 лет в нем нашли ошибку. Другое доказательство было найдено в 1976 году. Одно из первых значимых математических решений, опиравшихся на компьютерные вычисления, тогда оно вызвало несколько скептическое отношение. В 1997 году предложили более доступное доказательство. Оно тоже позволяло находить четырехцветную раскраску, но алгоритмически было медленным при применении к большим картам.
Болезнь четырех красок
Авторы нового исследования разработали оптимальный алгоритм раскраски любой карты в четыре цвета.
«Прежние работы доказывали возможность раскрасить карту четырьмя цветами — но не помогали легко и быстро сделать это. Новый алгоритм эффективнее и дает гораздо более простой способ раскраски», — говорит профессор Миккель Торуп из Копенгагенского университета, руководивший исследованием.
Около 10 лет он вместе с соавторами из Дании и Японии работал над теоремой о четырех красках, или, как называет ее информатик, «болезнью четырех красок».
«Вера в то, что для такого простого утверждения должно существовать простое доказательство, действительно чем-то похожа на болезнь. Думаю, по меньшей мере тысяча математиков подхватила болезнь четырех красок, потратив месяцы на попытки заставить ее работать, но так и не преуспев. Это болезнь, которой люди страдают с 1852 года», — считает Торуп.
Он признает, что математика присуща некоторая одержимость: «Потому что математики слегка сумасшедшие. Большая часть того, чем они занимаются, — это очень занудные вопросы. Мы становимся одержимы такими задачами, потому что они бросают вызов человеческому интеллекту. А если находим решение — то зачастую получаем ответы и на другие математические задачи».
Новое решение
В основе нового решения проблемы четырех красок — сделанное ранее открытие. С точки зрения математики карту можно считать планарным графом. Исследователи обнаружили, что графы содержат гораздо больше так называемых сводимых конфигураций, нежели считалось до сих пор. Это небольшие участки графа, которые дают математикам отправную точку для построения раскраски.
«Представьте сводимые конфигурации как ручки, за которые можно ухватиться, чтобы начать раскрашивать в четыре цвета. Мы показываем, что в графах есть не одна ручка, а поразительно много. Раньше этого никто не знал», — объясняет профессор Карстен Томассен из Датского технического университета, соавтор работы.
Поскольку теперь исследователи могут находить «ручки» во многих местах графа, тогда как раньше часто удавалось найти лишь одну, они могут начинать процесс раскраски из множества разных точек и потому гораздо быстрее раскрашивать даже очень большие карты.
«Мы перешли от того, что математики называют квадратичным временем, к линейному. Это означает, что если на карте в десять раз больше областей, вычисление становится всего в десять раз медленнее. С прежним алгоритмом оно замедлялось бы в 100 раз», — подчеркивает Томассен.
Что дальше
Это решение — это не только способ раскрашивать карты. Новое понимание структуры графов выходит за рамки классической проблемы четырех красок и открывает возможности для изучения гораздо более сложных типов графов и поверхностей.
«Благодаря обилию ручек идею можно применить и к другим видам поверхностей, помимо плоской карты. Например, к поверхностям с отверстиями — таким как плавательный круг или кусок эмментальского сыра. Именно поэтому мы полагаем, что результат может иметь значение далеко за пределами теоремы о четырех красках», — резюмирует Торуп.







