Доброго времени суток, Хабровчане!
В последнее время проблемы века стали очень популярными. Ими интересуется каждый себя уважающий математик. Сегодня Вашему вниманию хочу представить одну из проблем века, а именно — Проблема четырех красок и ее решение.
Проблема четырёх красок предложенна в 1852 году Фрэнсисом Гутри
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Стоит отметить две необходимые характеристики этой карты:
- Граница между любыми двумя областями является непрерывной линией.
- Каждая область является односвязной.
Данная проблема изначально легка и ее решение приходит на ум почти сразу, но нет доказательства, а именно — алгоритма, по которому можно было бы раскрасить любую карту.
Единственным принятым доказательством, является выведенное из идей Альфреда Кэмпе в 1880 году (его изначальное доказательство увидело свет в 1879 году[1]), что любую карту можно раскрасить в 5 цветов.
Почти сорок лет назад, в 1976 году, в Иллинойском университете, Кеннет Аппель и Вольфганг Хакен предоставили доказательство. В качестве доказателства послужила компьютерная симуляция, которая перебирала все возможные конфигурации карт и выявила минимальное количество цветов равных четырем. Алгоритм симуляции пытались многократно упростить, чтобы проверить доказательство, но к сожелению, безуспешно. Эти события вызвали сомнения у многих математиков, тем более, что описание симуляции занимало аж 741 страницу.
Решение
Для того, чтобы решить задачу четырех красок, необходимо найти такую фигуру Эвклидовой геометрии, у которой имеется наибольшее количество общих граней. А такая фигура известна, именно — Тетраэдр, у которого 4 грани связанны между собой каждая с каждой.
Что дает нам такая фигура?
Такая фигура может быть перенесена на сферу (как требует задача), где можно будет наглядно показать, как раскрасить данные части. В данном случае части тетраэдра будут раскрашены каждая в свой цвет, что даст 4 цвета. Так как это единственный способ как получить максимальное количество плоских фигур соприкасающимися между собой, это единственное минимальное количество цветов, которым можно раскрасить любую карту.
Тетраэдр можно разложить только на сфере (с соединенными гранями каждая с каждой), при этом такое разложение тетраэдра займет всю площадь сфера. Но это не означает, что на сфере могут быть расположены лишь эти 4 области. Со всей своей легкостью, внутри каждой из областей может находиться любая конфигурация областей, которые без затруднений можно раскрасить чередуя цвета.
Такой способ имеет исключения с количеством областей от 1 до 3, где количество областей равно цветам раскраски.
[1] A. B. Kempe. On the geographical problem of the four colors // Amer. J. Math… — 1879. — Т. 2. — С. 193—200.
Автор: uLow
