Проблема четырёх красок
Материал из Википедии — свободной энциклопедии
Проблема четырёх красок — математическая задача, предложенная Госри (англ. Guthrie) в 1852 году.
|
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы в виде дуги, были раскрашены в разные цвета. |
Содержание |
[править] Эквивалентные формулировки
|
Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, чтобы стороны каждого треугольника были раскрашены в разные цвета. |
[править] О доказательстве
К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.
[править] Вариации и обобщения
Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т.д.) оказались значительно проще.
[править] Литература
- А.А.Зыков, Основы теории графов, М.: Вузовская книга, 2004, с.367—386.
- Р.Курант, Г.Роббинс, Что такое математика?
- Самохин А. В. Проблема четырех красок: неоконченная история доказательства // СОЖ, 2000, No 7, с. 91—96.
- Родионов В.В., Методы четырехцветной раскраски вершин плоских графов, М.: КомКнига, 2005.-48 c. ISBN 5-484-00127-7
[править] на английском
- R.Diestel, Graph Theory, Electronic Edition, NY: Springer-Verlag, 2005, P. 137.
- Thomas, Robin, The Four Color Theorem,
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
