Математики нашли быстрый способ решить головоломку, над которой бились 174 года

Два профессора из Копенгагенского университета и Технического университета Дании (DTU) вместе с зарубежными коллегами разработали оптимальный алгоритм для быстрого решения задачи о четырёх красках. Математики пытались решить эту теорему 174 года.

✍️ Скоро читатели смогут публиковать свои тексты на Лайфхакере. Станьте первыми!

В 1852 году математик Фрэнсис Гутри заметил, что при составлении карты графств Англии ему хватило всего четырёх цветов, чтобы соседние области не совпадали по окраске, и предположил, что это правило работает для любой карты. Первое обоснование гипотезы представили в 1878‑м, но спустя 11 лет в нём нашли ошибку. Полное доказательство появилось только в 1976‑м, однако оно вызвало споры из-за опоры на сложные компьютерные расчёты, которые другим исследователям было трудно проверить. В 1997‑м учёные предложили более доступный вариант, но его алгоритм работал слишком медленно на крупных картах.

В отличие от прежних подходов, которые лишь доказывали принципиальную возможность раскрасить любую карту четырьмя цветами, новый метод датских исследователей позволяет быстро подобрать оттенки для каждого отдельного региона даже на очень больших картах.

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

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

Представьте сводимые конфигурации как ручки, за которые можно ухватиться, чтобы начать раскрашивание в четыре цвета. Мы показали, что в графах есть не одна такая ручка, а множество. Раньше этого никто не знал.

Карстен Томассен

Один из авторов исследования

Теперь исследователи могут находить «маркеры» во многих местах на графе. Благодаря этому подбор цветов можно запускать сразу с разных точек и гораздо быстрее справляться даже с очень большими картами. «Это значит, что если на карте в десять раз больше регионов, вычисления замедляются примерно в десять раз. Со старым алгоритмом скорость падала бы примерно в сто раз», — пояснил Томассен.

Миккель Торуп, ещё один из авторов решения, с юмором объяснил многолетнюю одержимость этой задачей, назвав её «болезнью четырёх цветов»: «Болезнь заключается в вере, что у такого простого утверждения должно быть простое доказательство. Я бы предположил, что ею заразились не меньше 1 000 математиков, которые тратили месяцы на попытки решить задачу, но так и не добивались полного успеха».

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

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

Источник: lifehacker.ru

0 0 голоса
Рейтинг новости
1
0
Подписаться
Уведомить о
0 комментариев