Математики нашли новое доказательство знаменитой проблемы четырёх красок спустя 30 лет
Международная группа учёных впервые за три десятилетия обновила доказательство легендарной теоремы о раскраске карт и в десятки тысяч раз ускорила ключевые алгоритмы для цифровых систем.
Международная группа учёных впервые за три десятилетия обновила доказательство легендарной теоремы о раскраске карт и в десятки тысяч раз ускорила ключевые алгоритмы для цифровых систем.
Международная команда математиков из Дании, Японии и Канады представила новое доказательство знаменитой теоремы о четырёх красках — одной из самых коварных головоломок в истории науки
Суть загадки родилась в 1852 году, когда студент из Лондона Фрэнсис Гатри раскрашивал карту Англии. Он заметил странную закономерность: чтобы ни у каких двух соседних графств не совпадал цвет, трёх красок всегда не хватает, пять — уже явно с избытком, а вот четырёх цветов всегда оказывается достаточно для карты абсолютно любой сложности. Единственное строгое правило задачи: соседними считаются регионы с общей границей-линией, а касание в одной точке (как на шахматной доске) соседством не признаётся. Вопрос казался наивной школьной забавой, но лучшие профессора Великобритании не смогли объяснить, почему четырёх красок всегда хватает для плоскости, и застряли в тупике.
В 1879 году лондонский математик Альфред Кемп заявил, что доказал теорему, придумав изящный трюк — так называемые цепочки Кемпа. Он предложил менять цвета целыми цепочками соседних стран так, чтобы освобождать нужный цвет для спорного региона. Научный мир признал победу, работу напечатал журнал Nature, а автор купался в славе 11 лет. Триумф рухнул в 1890 году: учёный Перси Хивуд наглядно показал, что логика Кемпа ломается, как только в центре карты оказывается область с пятью соседями. В этом случае цепочки перекраски накладываются друг на друга и взаимно уничтожаются, а карта остаётся нераскрашенной. Доказать удалось лишь то, что хватит пяти цветов, а вот для четырёх доказательство развалилось.
Решить проблему вручную оказалось невозможно: для строгого ответа требовалось нарисовать и проверить тысячи сложнейших комбинаций границ. Лишь в 1976 году математики из Иллинойса впервые в истории доверили доказательство суперкомпьютеру, который молотил данные 1200 часов и перебрал 1482 базовых фрагмента карт. Тогда это вызвало скандал в академической среде, ведь ни один человек не мог перепроверить машинный код вручную карандашом на бумаге.
Группа математиков: датчане Миккель Труп и Карстен Томассен, японец Кен-ити Каварабайаши и канадец Бойян Мохар — в своей свежей работе перевернула алгоритмическую сторону задачи. Учёные проверили уже 8202 конфигурации, но научили алгоритм упрощать огромные карты не по отдельным фрагментам, а целыми параллельными блоками. В итоге скорость вычислений взлетела в 50 тысяч раз: для карт на миллион областей перебор теперь занимает доли секунды, что на практике критически важно для маршрутизации сотовых вышек, распределения частот радиосвязи и планирования микросхем.
