Рубрика «алгоритм» - 10

Доброго времени суток, Хабровчане!
В последнее время проблемы века стали очень популярными. Ими интересуется каждый себя уважающий математик. Сегодня Вашему вниманию хочу представить одну из проблем века, а именно — Проблема четырех красок и ее решение.

Проблема четырёх красок предложенна в 1852 году Фрэнсисом Гутри

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

Стоит отметить две необходимые характеристики этой карты:

• Граница между любыми двумя областями является непрерывной линией.
• Каждая область является односвязной.

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

Единственным принятым доказательством, является выведенное из идей Альфреда Кэмпе в 1880 году (его изначальное доказательство увидело свет в 1879 году[1]), что любую карту можно раскрасить в 5 цветов.

Почти сорок лет назад, в 1976 году, в Иллинойском университете, Кеннет Аппель и Вольфганг Хакен предоставили доказательство. В качестве доказателства послужила компьютерная симуляция, которая перебирала все возможные конфигурации карт и выявила минимальное количество цветов равных четырем. Алгоритм симуляции пытались многократно упростить, чтобы проверить доказательство, но к сожелению, безуспешно. Эти события вызвали сомнения у многих математиков, тем более, что описание симуляции занимало аж 741 страницу.
Читать полностью »