WikiSort.ru - Не сортированное

Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски карты на плоскости эквивалентна задаче на сфере.

В 1852 году Фрэнсисом Гутри^[en], составляя карту графств Англии, обратил внимание, что для такой цели хватает четырёх красок, Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де. Моргану, а тот — математической общественности. Точную формулировку гипотезы опубликовал А. Кэли (1878)^[1]. Доказать теорему долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок^[2].

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

Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем (англ.) и Вольфгангом Хакеном (англ.) из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определённый набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать какую-нибудь из этих 1936 карт, чего нет. Это противоречие говорит о том, что контрпримера нет вообще.

Изначально доказательство было принято не всеми математиками, поскольку его невозможно проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)^[3].

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

В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:

• Хроматическое число планарного графа не превосходит 4^[4].
• Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета.^{[источник не указан 230 дней]}
• Известно ещё множество эквивалентных формулировок^[4].

Исторические попытки доказательства

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

• Альфред Кэмпе предложил доказательство в 1879 году^[5], его опровергли в 1890 году, но на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов^[2].
• Питер Тэт предложил другое доказательство в 1880 году^[2][6], его опровергли в 1891 году.

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

Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т. д.) оказались значительно проще. Для всех замкнутых поверхностей, кроме сферы (и ей эквивалентных плоскости и цилиндра) и бутылки Клейна, необходимое число красок может быть вычислено через эйлерову характеристику ${\displaystyle \chi }$ по формуле, предложенной в 1890 году Перси Джоном Хивудом^[en][7] и окончательно доказанной на протяжении 1952—1968 годов группой математиков с наибольшим вкладом Герхарда Рингеля и Джона Янгса^{[en][8][9][10]}

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

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

Для односторонних поверхностей рода ${\displaystyle g}$ ^[9]

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

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

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

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

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

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

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

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

В культуре

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

См. также

• Доказательные вычисления
• Задача Нельсона — Эрдёша — Хадвигера

Примечания

Литература

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

Иэн Стюарт. "Величайшие математические задачи"

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