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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Проблема четырёх красок
Административная карта России, раскрашенная в четыре цвета

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

Задача раскраски карты на плоскости эквивалентна задаче на сфере.

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

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

Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения.

Эквивалентные формулировки[править | править исходный текст]

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

История доказательства[править | править исходный текст]

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

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

Вариации и обобщения[править | править исходный текст]

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

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

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

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

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

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

Игра «четыре краски»[править | править исходный текст]

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

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

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

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

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

В культуре[править | править исходный текст]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. A. B. Kempe. On the geographical problem of the four colors // Amer. J. Math.. — 1879. — Т. 2. — С. 193—200.
  2. P. G. Tait. Note on a theorem in geometry of position // Trans. Roy. Soc. Edinburgh. — 1880. — Т. 29. — С. 657—660.
  3. В. А. Горбатов. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. Физматлит, 2000. — С. 253-254. — 544 с. — 2000 экз. — ISBN 5-02-015238-2
  4. Percy John Heawood. Map-Colour Theorem // Quarterly Journal of Mathematics, Oxford. — 1890. — Т. 24. — С. 332–338.
  5. 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.
  6. 1 2 Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с.
  7. P. Franklin. A Six Colour Problem // J. Math. Phys. — 1934. — Т. 13. — С. 363—369.
  8. Мартин Гарднер. Проблема четырёх красок // Математические головоломки и развлечения = Mathematical puzzles and diversions. — 2-е изд. — М.: «Мир», 1999. — С. 389-390. — 447 с. — ISBN 5-03-003340-8
  9. Martin Gardner. The Island Of Five Colours. — N.Y.: Fantasia Mathematica, 1958.

Литература[править | править исходный текст]