[Из песочницы] Проблема четырех красок. Решение
Доброго времени суток, Хабровчане!В последнее время проблемы века стали очень популярными. Ими интересуется каждый себя уважающий математик. Сегодня Вашему вниманию хочу представить одну из проблем века, а именно — Проблема четырех красок и ее решение.
Проблема четырёх красок предложенна в 1852 году Фрэнсисом Гутри
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Стоит отметить две необходимые характеристики этой карты:
- Граница между любыми двумя областями является непрерывной линией.
- Каждая область является односвязной.
Данная проблема изначально легка и ее решение приходит на ум почти сразу, но нет доказательства, а именно — алгоритма, по которому можно было бы раскрасить любую карту.
Единственным принятым доказательством, является выведенное из идей Альфреда Кэмпе в 1880 году (его изначальное доказательство увидело свет в 1879 году[1]), что любую карту можно раскрасить в 5 цветов.
Почти сорок лет назад, в 1976 году, в Иллинойском университете, Кеннет Аппель и Вольфганг Хакен предоставили доказательство. В качестве доказателства послужила компьютерная симуляция, которая перебирала все возможные конфигурации карт и выявила минимальное количество цветов равных четырем. Алгоритм симуляции пытались многократно упростить, чтобы проверить доказательство, но к сожелению, безуспешно. Эти события вызвали сомнения у многих математиков, тем более, что описание симуляции занимало аж 741 страницу.
Читать дальше →
