04-06-2023
Проблема четырёх красок — математическая задача, предложенная Ф. Гутри (англ.) в 1852 году, сформулированная следующим образом:
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. |
Стоит отметить две необходимые характеристики этой карты:
Переформулировать эту задачу можно так: показать, что хроматическое число плоского графа (c определенными ограничениями в соответствии с понятием «карта» в данной теореме) не превосходит 4.
Содержание |
Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, чтобы все стороны каждого треугольника были раскрашены в разные цвета. |
Кеннет Аппель (Kenneth Appel) и Вольфганг Хакен (Wolfgang Haken) из Иллинойского университета доказали в 1976 году, что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок[1]. Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.
Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер[2] в 2000 году.
Наиболее известные попытки доказательства:
Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т. д.) оказались значительно проще. Для всех замкнутых поверхностей, кроме сферы (и ей эквивалентных плоскости и цилиндра) и бутылки Клейна, необходимое число красок может быть вычислено через эйлерову характеристику по формуле, предложенной в 1890 году Перси Джоном Хивудом (Percy John Heawood)[7] и окончательно доказанной на протяжении 1952—1968 годов группой математиков с наибольшим вкладом Герхарда Рингеля и Теда Янгса (Gerhard Ringel and J. T. W. Youngs)[8][9]
Для бутылки Клейна число равно 6 (а не 7, как по формуле) — это показал П. Франклин в 1934 году,[10] а для сферы — 4.
Для односторонних поверхностей[9]
В старших размерностях разумного обобщения задачи не существует, так как легко придумать уже трёхмерную карту с произвольным числом областей, которые все друг друга касаются.
Стивен Барр предложил логическую игру на бумаге для двух игроков, названную «Четыре краски». По словам Мартина Гарднера — «Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру»[11].
Для этой игры нужны четыре цветных карандаша. Первый игрок начинает игру, рисуя произвольную пустую область. Второй игрок закрашивает её любым из четырёх цветов и в свою очередь рисует свою пустую область. Первый игрок закрашивает область второго игрока и добавляет новую область, и так далее — каждый игрок раскрашивает область соперника и добавляет свою. При этом области, имеющие общую границу, должны быть раскрашены в разные цвета. Проигрывает тот, кто на своём ходу вынужден будет взять пятую краску.
Стоит отметить, что в этой игре проигрыш одного из игроков вовсе не является доказательством неверности теоремы (четырех красок оказалось недостаточно!). А лишь иллюстрацией того, что условия игры и теоремы весьма разнятся. Чтобы проверить верность теоремы для полученной в игре карты, нужно проверить связность нарисованных областей и, удалив с нее цвета, выяснить, можно ли обойтись лишь четырьмя цветами для закрашивания получившейся карты (теорема утверждает, что можно).
Существуют также следующие вариации игры:
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Проблема четырёх красок.