«Четырёхцветная болезнь»: как математики сделали прорыв спустя 174 года

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

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

С тех пор задача не отпускает исследователей. Один из авторов нового алгоритма, специалист по информатике из Копенгагенского университета, сравнивает собственную одержимость с болезнью. По его оценке, «четырёхцветной болезнью» переболели не менее тысячи математиков, месяцами безуспешно пытавшихся довести дело до конца, а сам недуг преследует людей с 1852 года. Лекарство нашлось после десяти лет работы, когда команда обнаружила у плоских графов, то есть математических моделей карт, неожиданное свойство. Приводимых конфигураций, которые служат отправными точками для раскраски, в них гораздо больше, чем предполагалось прежде. Другой специалист из Технического университета Дании сравнивает такие конфигурации с ручками, за которые можно ухватиться, и подчёркивает, что в графе их не одна, а поразительно много, чего раньше никто не знал.

Обилие «ручек» позволило начинать раскраску одновременно в разных частях карты, и время вычислений сократилось с квадратичного до линейного. Проще говоря, если число областей вырастет в десять раз, расчёт замедлится примерно в десять раз, тогда как прежний алгоритм потребовал бы в сто раз больше времени. Метод применим и к более сложным поверхностям, например к тем, что имеют отверстия, будь то спасательный круг или кусок сыра. Практическая польза для повседневной жизни пока неочевидна, однако учёные не жалеют о потраченных годах.

Оцените статью
Поделись знанием

Рекомендуем

1
Как понять, что тебе нужна математика: советы от автора Сириус. Курсов #математика #Сириус.Курсы 13 сентября 2023 12:08
2
Как Сириус объединяет математиков со всего мира #образование #Сириус #математика 26 января 2025 06:42
3
Скандал с ИИ: кто решил математическую задачу тысячелетия? #искусственный интеллект #математика 16 сентября 2026 15:37