Технологии

Четырёх цветов хватает для любой карты: математики нашли способ раскрашивать её в разы быстрее

19 ноября 7 просмотров 1 минута на чтение
Размер шрифта: А А А

Представьте, что перед вами карта с любым количеством стран, областей или городов. Задача проста: раскрасить её так, чтобы любые две соседние территории имели разные цвета. Оказывается, для любой, даже самой запутанной плоской карты, достаточно всего четырех цветов. Этот тезис, сформулированный Фрэнсисом Гатри еще в 1852 году, стал одной из самых "вязких" задач в истории математики: первое доказательство нашли в 1879-м, но оно оказалось ошибочным, а окончательный ответ удалось получить только в 1976 году с помощью компьютерной программы.
От доказательства к эффективности

С точки зрения математики теорема четырех цветов считается решенной. Однако для специалистов существовал огромный разрыв между знанием того, что "это возможно", и наличием быстрого, эффективного способа сделать это на практике. Предыдущие алгоритмы работали крайне медленно: при увеличении размера карты время вычислений росло квадратично. Если количество регионов на карте увеличивалось в 10 раз, компьютер тратил на расчеты в 100 раз больше времени. Это превращало задачу в вычислительный кошмар при работе с масштабными данными.
Спустя десятилетия анализа международная группа исследователей, включая Миккеля Торупа из Копенгагенского университета и Карстена Томассена из Технического университета Дании, представила на конференции Foundations of Computer Science (FOCS) новый алгоритм. Это не новое доказательство самой теоремы, а поиск оптимального метода её реализации.

Четырёх цветов хватает для любой карты: математики нашли способ раскрашивать её в разы быстрее
Читать полностью на сайте www.pravda.ru