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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В культуре

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

См. также

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

Литература

• А. А. Зыков. Основы теории графов. — М.: Вузовская книга, 2000. — С. 367—386.
• Р. Курант, Г. Роббинс [www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?]
• Самохин А. В. [window.edu.ru/window_catalog/files/r20367/0007_091.pdf Проблема четырех красок: неоконченная история доказательства] // СОЖ. — 2000. — № 7. — С. 91—96.
• Родионов В. В. Методы четырехцветной раскраски вершин плоских графов. — М.: КомКнига, 2000. — 48 с. — 2005 экз. — ISBN 5-484-00127-7.
• Thomas, Robin [www.math.gatech.edu/~thomas/FC/fourcolor.html The Four Color Theorem]
• Рингель Г. Теорема о раскраске карт / Перевод с английского В. Б. Алексеева. — М.: Мир, 1977. — 256 с. — книга с доказательством проблемы для всех поверхностей, кроме плоскости и сферы
• Болтянский В. Г.,Ефремович В. А. Наглядная топология. — М.: Наука, 1982. — 160 с. — (Библиотечка «Квант»).

Отрывок, характеризующий Проблема четырёх красок

Пуфф! – вдруг виднелся круглый, плотный, играющий лиловым, серым и молочно белым цветами дым, и бумм! – раздавался через секунду звук этого дыма.
«Пуф пуф» – поднимались два дыма, толкаясь и сливаясь; и «бум бум» – подтверждали звуки то, что видел глаз.
Пьер оглядывался на первый дым, который он оставил округлым плотным мячиком, и уже на месте его были шары дыма, тянущегося в сторону, и пуф… (с остановкой) пуф пуф – зарождались еще три, еще четыре, и на каждый, с теми же расстановками, бум… бум бум бум – отвечали красивые, твердые, верные звуки. Казалось то, что дымы эти бежали, то, что они стояли, и мимо них бежали леса, поля и блестящие штыки. С левой стороны, по полям и кустам, беспрестанно зарождались эти большие дымы с своими торжественными отголосками, и ближе еще, по низам и лесам, вспыхивали маленькие, не успевавшие округляться дымки ружей и точно так же давали свои маленькие отголоски. Трах та та тах – трещали ружья хотя и часто, но неправильно и бедно в сравнении с орудийными выстрелами.
Пьеру захотелось быть там, где были эти дымы, эти блестящие штыки и пушки, это движение, эти звуки. Он оглянулся на Кутузова и на его свиту, чтобы сверить свое впечатление с другими. Все точно так же, как и он, и, как ему казалось, с тем же чувством смотрели вперед, на поле сражения. На всех лицах светилась теперь та скрытая теплота (chaleur latente) чувства, которое Пьер замечал вчера и которое он понял совершенно после своего разговора с князем Андреем.
– Поезжай, голубчик, поезжай, Христос с тобой, – говорил Кутузов, не спуская глаз с поля сражения, генералу, стоявшему подле него.
Выслушав приказание, генерал этот прошел мимо Пьера, к сходу с кургана.
– К переправе! – холодно и строго сказал генерал в ответ на вопрос одного из штабных, куда он едет. «И я, и я», – подумал Пьер и пошел по направлению за генералом.
Генерал садился на лошадь, которую подал ему казак. Пьер подошел к своему берейтору, державшему лошадей. Спросив, которая посмирнее, Пьер взлез на лошадь, схватился за гриву, прижал каблуки вывернутых ног к животу лошади и, чувствуя, что очки его спадают и что он не в силах отвести рук от гривы и поводьев, поскакал за генералом, возбуждая улыбки штабных, с кургана смотревших на него.


Генерал, за которым скакал Пьер, спустившись под гору, круто повернул влево, и Пьер, потеряв его из вида, вскакал в ряды пехотных солдат, шедших впереди его. Он пытался выехать из них то вправо, то влево; но везде были солдаты, с одинаково озабоченными лицами, занятыми каким то невидным, но, очевидно, важным делом. Все с одинаково недовольно вопросительным взглядом смотрели на этого толстого человека в белой шляпе, неизвестно для чего топчущего их своею лошадью.
– Чего ездит посерёд батальона! – крикнул на него один. Другой толконул прикладом его лошадь, и Пьер, прижавшись к луке и едва удерживая шарахнувшуюся лошадь, выскакал вперед солдат, где было просторнее.
Впереди его был мост, а у моста, стреляя, стояли другие солдаты. Пьер подъехал к ним. Сам того не зная, Пьер заехал к мосту через Колочу, который был между Горками и Бородиным и который в первом действии сражения (заняв Бородино) атаковали французы. Пьер видел, что впереди его был мост и что с обеих сторон моста и на лугу, в тех рядах лежащего сена, которые он заметил вчера, в дыму что то делали солдаты; но, несмотря на неумолкающую стрельбу, происходившую в этом месте, он никак не думал, что тут то и было поле сражения. Он не слыхал звуков пуль, визжавших со всех сторон, и снарядов, перелетавших через него, не видал неприятеля, бывшего на той стороне реки, и долго не видал убитых и раненых, хотя многие падали недалеко от него. С улыбкой, не сходившей с его лица, он оглядывался вокруг себя.
– Что ездит этот перед линией? – опять крикнул на него кто то.
– Влево, вправо возьми, – кричали ему. Пьер взял вправо и неожиданно съехался с знакомым ему адъютантом генерала Раевского. Адъютант этот сердито взглянул на Пьера, очевидно, сбираясь тоже крикнуть на него, но, узнав его, кивнул ему головой.
– Вы как тут? – проговорил он и поскакал дальше.
Пьер, чувствуя себя не на своем месте и без дела, боясь опять помешать кому нибудь, поскакал за адъютантом.
– Это здесь, что же? Можно мне с вами? – спрашивал он.
– Сейчас, сейчас, – отвечал адъютант и, подскакав к толстому полковнику, стоявшему на лугу, что то передал ему и тогда уже обратился к Пьеру.
– Вы зачем сюда попали, граф? – сказал он ему с улыбкой. – Все любопытствуете?
– Да, да, – сказал Пьер. Но адъютант, повернув лошадь, ехал дальше.
– Здесь то слава богу, – сказал адъютант, – но на левом фланге у Багратиона ужасная жарня идет.
– Неужели? – спросил Пьер. – Это где же?
– Да вот поедемте со мной на курган, от нас видно. А у нас на батарее еще сносно, – сказал адъютант. – Что ж, едете?
– Да, я с вами, – сказал Пьер, глядя вокруг себя и отыскивая глазами своего берейтора. Тут только в первый раз Пьер увидал раненых, бредущих пешком и несомых на носилках. На том самом лужке с пахучими рядами сена, по которому он проезжал вчера, поперек рядов, неловко подвернув голову, неподвижно лежал один солдат с свалившимся кивером. – А этого отчего не подняли? – начал было Пьер; но, увидав строгое лицо адъютанта, оглянувшегося в ту же сторону, он замолчал.
Пьер не нашел своего берейтора и вместе с адъютантом низом поехал по лощине к кургану Раевского. Лошадь Пьера отставала от адъютанта и равномерно встряхивала его.
– Вы, видно, не привыкли верхом ездить, граф? – спросил адъютант.
– Нет, ничего, но что то она прыгает очень, – с недоуменьем сказал Пьер.
– Ээ!.. да она ранена, – сказал адъютант, – правая передняя, выше колена. Пуля, должно быть. Поздравляю, граф, – сказал он, – le bapteme de feu [крещение огнем].
Проехав в дыму по шестому корпусу, позади артиллерии, которая, выдвинутая вперед, стреляла, оглушая своими выстрелами, они приехали к небольшому лесу. В лесу было прохладно, тихо и пахло осенью. Пьер и адъютант слезли с лошадей и пешком вошли на гору.
– Здесь генерал? – спросил адъютант, подходя к кургану.
– Сейчас были, поехали сюда, – указывая вправо, отвечали ему.
Адъютант оглянулся на Пьера, как бы не зная, что ему теперь с ним делать.
– Не беспокойтесь, – сказал Пьер. – Я пойду на курган, можно?
– Да пойдите, оттуда все видно и не так опасно. А я заеду за вами.
Пьер пошел на батарею, и адъютант поехал дальше. Больше они не видались, и уже гораздо после Пьер узнал, что этому адъютанту в этот день оторвало руку.
Курган, на который вошел Пьер, был то знаменитое (потом известное у русских под именем курганной батареи, или батареи Раевского, а у французов под именем la grande redoute, la fatale redoute, la redoute du centre [большого редута, рокового редута, центрального редута] место, вокруг которого положены десятки тысяч людей и которое французы считали важнейшим пунктом позиции.
Редут этот состоял из кургана, на котором с трех сторон были выкопаны канавы. В окопанном канавами место стояли десять стрелявших пушек, высунутых в отверстие валов.
В линию с курганом стояли с обеих сторон пушки, тоже беспрестанно стрелявшие. Немного позади пушек стояли пехотные войска. Входя на этот курган, Пьер никак не думал, что это окопанное небольшими канавами место, на котором стояло и стреляло несколько пушек, было самое важное место в сражении.
Пьеру, напротив, казалось, что это место (именно потому, что он находился на нем) было одно из самых незначительных мест сражения.
Войдя на курган, Пьер сел в конце канавы, окружающей батарею, и с бессознательно радостной улыбкой смотрел на то, что делалось вокруг него. Изредка Пьер все с той же улыбкой вставал и, стараясь не помешать солдатам, заряжавшим и накатывавшим орудия, беспрестанно пробегавшим мимо него с сумками и зарядами, прохаживался по батарее. Пушки с этой батареи беспрестанно одна за другой стреляли, оглушая своими звуками и застилая всю окрестность пороховым дымом.
В противность той жуткости, которая чувствовалась между пехотными солдатами прикрытия, здесь, на батарее, где небольшое количество людей, занятых делом, бело ограничено, отделено от других канавой, – здесь чувствовалось одинаковое и общее всем, как бы семейное оживление.
Появление невоенной фигуры Пьера в белой шляпе сначала неприятно поразило этих людей. Солдаты, проходя мимо его, удивленно и даже испуганно косились на его фигуру. Старший артиллерийский офицер, высокий, с длинными ногами, рябой человек, как будто для того, чтобы посмотреть на действие крайнего орудия, подошел к Пьеру и любопытно посмотрел на него.
Молоденький круглолицый офицерик, еще совершенный ребенок, очевидно, только что выпущенный из корпуса, распоряжаясь весьма старательно порученными ему двумя пушками, строго обратился к Пьеру.
– Господин, позвольте вас попросить с дороги, – сказал он ему, – здесь нельзя.
Солдаты неодобрительно покачивали головами, глядя на Пьера. Но когда все убедились, что этот человек в белой шляпе не только не делал ничего дурного, но или смирно сидел на откосе вала, или с робкой улыбкой, учтиво сторонясь перед солдатами, прохаживался по батарее под выстрелами так же спокойно, как по бульвару, тогда понемногу чувство недоброжелательного недоуменья к нему стало переходить в ласковое и шутливое участие, подобное тому, которое солдаты имеют к своим животным: собакам, петухам, козлам и вообще животным, живущим при воинских командах. Солдаты эти сейчас же мысленно приняли Пьера в свою семью, присвоили себе и дали ему прозвище. «Наш барин» прозвали его и про него ласково смеялись между собой.
Одно ядро взрыло землю в двух шагах от Пьера. Он, обчищая взбрызнутую ядром землю с платья, с улыбкой оглянулся вокруг себя.