Как раскрасить географическую карту?

В 1852 г. английский математик Фрэнсис Гатри составлял карту графств Великобритании. У него возник вопрос: какое минимальное количество цветов нужно, чтобы раскрасить карту любой конфигурации? Разумеется, соседние графства должны иметь разный цвет. Гатри предположил, что достаточно четырех цветов. Но доказать это не удалось ни ему, ни его коллегам на протяжении последних 124 лет. В результате четырех лет упорной работы и 1200 часов машинного времени решение нашли в 1976 г. ученые из Чикагского университета — Кеннет Аппель и Вольфганг Хакен.

Поскольку ни один человек, даже математик, не может воспроизвести то, на что более 1000 часов тратит компьютер, доказательство проблемы о четырех красках сначала вызвало споры среди специалистов. В первые годы после публикации в ней находили все новые ошибки. Но Аппель и Хакен каждый раз устраняли их. Сейчас их работа считается признанной. К тому же математики нашли другие, не столь сложные, доказательства этой задачи. Но никому из них не удалось полностью обойтись без помощи компьютера.


Поделиться ссылкой