Проблема четырёх красок

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Ф. Гутри (англ.) в 1852 году, сформулированная следующим образом:

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

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

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

Переформулировать эту задачу можно так: показать, что хроматическое число плоского графа (c определенными ограничениями в соответствии с понятием «карта» в данной теореме) не превосходит 4.

Эквивалентные формулировки

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

О доказательстве

Кеннет Аппель (Kenneth Appel) и Вольфганг Хакен (Wolfgang Haken) из Иллинойского университета доказали в 1976 году, что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок^[1]. Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер^[2] в 2000 году.

История доказательства

Наиболее известные попытки доказательства:

• Альфред Кэмпе предложил доказательство в 1879 году^[3], его опровергли в 1880 году, на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов.
• Питер Тэт предложил другое доказательство в 1880 году^[4], его опровергли в 1891 году.
• В своей книге^[5] В. А. Горбатов утверждает, что предложил классическое доказательство ещё в 1964 году (объёмом около 30 стр.). Однако опровержений, как и подтверждений, это доказательство пока не получило, см. также^[6].

Вариации и обобщения

Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т. д.) оказались значительно проще. Для всех замкнутых поверхностей, кроме сферы (и ей эквивалентных плоскости и цилиндра) и бутылки Клейна, необходимое число красок может быть вычислено через эйлерову характеристику $\chi$ по формуле, предложенной в 1890 году Перси Джоном Хивудом (Percy John Heawood)^[7] и окончательно доказанной на протяжении 1952—1968 годов группой математиков с наибольшим вкладом Герхарда Рингеля и Теда Янгса (Gerhard Ringel and J. T. W. Youngs)^[8][9]

$p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor.$

Для бутылки Клейна число равно 6 (а не 7, как по формуле) — это показал П. Франклин в 1934 году,^[10] а для сферы — 4.

Для односторонних поверхностей^[9]

$p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor.$.

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

Игра «четыре краски»

Стивен Барр предложил логическую игру на бумаге для двух игроков, названную «Четыре краски». По словам Мартина Гарднера — «Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру»^[11].

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

Стоит отметить, что в этой игре проигрыш одного из игроков вовсе не является доказательством неверности теоремы (четырех красок оказалось недостаточно!). А лишь иллюстрацией того, что условия игры и теоремы весьма разнятся. Чтобы проверить верность теоремы для полученной в игре карты, нужно проверить связность нарисованных областей и, удалив с нее цвета, выяснить, можно ли обойтись лишь четырьмя цветами для закрашивания получившейся карты (теорема утверждает, что можно).

Существуют также следующие вариации игры:

1. Карта заранее разбивается случайным образом на области различной величины, и каждый ход игры меняется игрок который закрашивает область, а также меняется цвет (в строгой последовательности). Таким образом каждый игрок закрашивает карту только двумя цветами, а в случае если не может закрасить так, чтобы области, имеющие общую границу были раскрашены в разные цвета. пропускает ход. Игра прекращается когда ни один из игроков больше не сможет сделать ни одного хода. Выигрывает тот, у кого общая площадь закрашенных им областей больше.
2. Квадрат разбит на несколько квадратов (в основном 4x4), и его стороны окрашены в один из четырех цветов (каждый в разный цвет). Первым ходом закрашивается квадрат прилегающий к стороне, каждый последующий ход можно закрашивать тот квадрат, который прилегает к одному из закрашенных квадратов. Нельзя закрашивать квадрат теми цветами, которыми закрашен один из прилегающих к нему квадратов (в том числе и по диагонали) или прилегающая к квадрату сторона. Выигрывает игрок делающий последний ход.

В культуре

• «Остров пяти красок» — фантастический рассказ Мартина Гарднера^[12].

См. также

• Доказательные вычисления

Примечания

1. ↑ R. Diestel. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005. — P. 137.
2. ↑ Ashay Dharwadker, The Four Colour Theorem, Proc. Institute of Mathematics, Amazon Books, ISBN 1466265302
3. ↑ A. B. Kempe. On the geographical problem of the four colors // Amer. J. Math.. — 1879. — Т. 2. — С. 193—200.
4. ↑ P. G. Tait. Note on a theorem in geometry of position // Trans. Roy. Soc. Edinburgh. — 1880. — Т. 29. — С. 657—660.
5. ↑ В. А. Горбатов. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. Физматлит, 2000. — С. 253-254. — 544 с. — 2000 экз. — ISBN 5-02-015238-2
6. ↑ Чечулин В. Л. Об одном варианте доказательства 4-раскрашиваемости плоских графов // Вестник ПГУ, серия Математика. Механика. Информатика. — Пермь, 2006. — № 4(4). — С. 86—87. Это доказательство естественным образом обобщается в доказательство гипотезы Хадвиггера (см. Чечулин В. Л., Теорема о стягивании конечных связных графов // Университетские исследования, 2011 http://www.uresearch.psu.ru/files/articles/483_11223.doc )
7. ↑ Percy John Heawood. Map-Colour Theorem // Quarterly Journal of Mathematics, Oxford. — 1890. — Т. 24. — С. 332–338.
8. ↑ G. Ringel and J. W. T. Youngs. Solution of the Heawood Map-Coloring Problem // Proc. Nat. Acad. Sci. USA. — 1968. — В. 2. — Т. 60. — С. 438–445. — DOI:10.1073/pnas.60.2.438 — PMID 16591648.
9. ↑ ^{1 2} Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с.
10. ↑ P. Franklin. A Six Colour Problem // J. Math. Phys. — 1934. — Т. 13. — С. 363—369.
11. ↑ Мартин Гарднер. Проблема четырёх красок // Математические головоломки и развлечения = Mathematical puzzles and diversions. — 2-е изд. — М.: «Мир», 1999. — С. 389-390. — 447 с. — ISBN 5-03-003340-8
12. ↑ Martin Gardner. The Island Of Five Colours. — N.Y.: Fantasia Mathematica, 1958.

Литература

	Проблема четырёх красок на Викискладе?

• А. А. Зыков. Основы теории графов. — М.: Вузовская книга, 2000. — С. 367—386.
• Р.Курант, Г.Роббинс Что такое математика?
• Самохин А. В. Проблема четырех красок: неоконченная история доказательства // СОЖ. — 2000. — № 7. — С. 91—96.
• Родионов В. В. Методы четырехцветной раскраски вершин плоских графов. — М.: КомКнига, 2000. — 48 с. — 2005 экз. — ISBN 5-484-00127-7
• Thomas, Robin The Four Color Theorem
• Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с. — книга с доказательством проблемы для всех поверхностей, кроме плоскости и сферы