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










