Теорема о четырёх красках

(перенаправлено с «Проблема четырёх красок»)

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

Карта общин Словении, раскрашенная в четыре цвета

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

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

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

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

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

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

Известно ещё множество эквивалентных формулировок[5].

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

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

  • Альфред Кэмпе предложил доказательство в 1879 году[7], его опровергли в 1890 году, но на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов[3].
  • Питер Тэйт предложил другое доказательство в 1880 году[3][8], его опровергли в 1891 году.
  • Малиев М. Задача о четырех красках, 1914.

Вариации и обобщенияПравить

Другие поверхностиПравить

 

Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т. д.) оказались значительно проще. Для всех замкнутых поверхностей, кроме сферы (и ей эквивалентных плоскости и цилиндра) и бутылки Клейна, необходимое число красок может быть вычислено по её роду   по следующей формуле, предложенной в 1890 году Перси Джоном Хивудом:[9]

 

Верхняя оценка получается довольно просто, она была доказана самим Хивудом (для сферы формула даёт правильный ответ — 4, однако доказательство Хивуда для неё не применимо). Нижняя доказывается вложением полного графа   в соответствующую поверхность; доказательство строилось в 1952—1968 годах группой математиков, последний шаг был сделан Герхардом Рингелем и Джоном Янгсом[en].[10][11][12]

 
Разбиение ленты Мёбиуса на шесть взаимно соприкасающихся областей

Для ленты Мёбиуса (также как и для проективной плоскости) требуется 6 цветов. Для односторонних поверхностей рода   справедливо[11]

 

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

Карта островаПравить

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

Задача об империяхПравить

Аналогичный вопрос для карт с колониальными империями (то есть со странами, состоящими из нескольких отдельных «кусков» на карте, число которых — m), рассматривался Перси Джоном Хивудом. При   ответ  . Верхняя оценка получается довольно просто, она была доказана самим Хивудом. Нижняя доказывается вложением полного графа   в соответствующую поверхность; доказательство дано Герхардом Рингелем и Брэдом Джексоном.[14]

Вариант задачи про империи с колониями на других планетах остаётся открытым. Например, если у каждой страны на Земле есть колония на Луне, то известны только оценки  

Старшие размерностиПравить

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

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

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

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

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

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

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

В культуреПравить

См. такжеПравить

ПримечанияПравить

  1. Франк Харари. Гипотеза четырёх красок // Теория графов = Graph Theory. — М.: Мир, 1973. — С. 17—18.
  2. Самохин А.В. Проблема четырёх красок: неоконченная история доказательства // Соровский образовательный журнал. — 2000. — Т. 6, № 7.
  3. 1 2 3 J. J. O'Connor, E. F. Robertson. The four colour theorem. MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland (сентябрь 1996).
  4. Georges Gonthier. A computer-checked proof of the Four Colour Theorem (англ.). Microsoft Research Cambridge (2005). Архивировано 5 июня 2022 года.
  5. 1 2 Шор Н. З., Донец Г. А. О задаче четырёх красок // Математика сегодня / под ред. проф. А. Я. Дороговцева — Киев, Вища школа, 1982. — Тираж 3000 экз. — c. 33-53
  6. Лакеев А.В. Элементы теории обыкновенных графов. — Иркутск: Изд-во ИГУ, 2014. — С. 7. — 92 с.
  7. A. B. Kempe. On the geographical problem of the four colors (англ.) // Amer. J. Math.. — 1879. — Vol. 2. — P. 193—200.
  8. P. G. Tait. Note on a theorem in geometry of position (англ.) // Trans. Roy. Soc. Edinburgh. — 1880. — Vol. 29. — P. 657—660.
  9. Percy John Heawood. Map-Colour Theorem (англ.) // Quarterly Journal of Mathematics, Oxford. — 1890. — Vol. 24. — P. 332—338.
  10. G. Ringel, J. W. T. Youngs. Solution of the Heawood Map-Coloring Problem (англ.) // Proc. Nat. Acad. Sci. USA. — 1968. — Vol. 60, iss. 2. — P. 438—445. — doi:10.1073/pnas.60.2.438. — PMID 16591648.
  11. 1 2 Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с.
  12. Болтянский, 1982, с. 77.
  13. P. Franklin. A Six Colour Problem (англ.) // J. Math. Phys. — 1934. — Vol. 13. — P. 363—369.
  14. Jackson, Brad; Ringel, Gerhard. Heawood’s empire problem (англ.) // J. Combin. Theory Ser. B. — 1985. — Vol. 38, no. 2. — P. 168—178.
  15. Мартин Гарднер. Проблема четырёх красок // Математические головоломки и развлечения = Mathematical puzzles and diversions : [пер. с англ.]. — 2-е изд. — М. : Мир, 1999. — С. 389—390. — 447 с. — ISBN 5-03-003340-8.
  16. Martin Gardner. The Island Of Five Colours. — N. Y.: Fantasia Mathematica, 1958.

ЛитератураПравить