Предисловие
Всем привет!
Думаю, многие из вас слышали о проблеме четырех красок. Это известная теорема, которую не могли доказать более ста лет. Она имеет очень простую формулировку: для раскраски любой карты достаточно четырех цветов.
Конечно, подразумевается, что соседние страны должны быть окрашены в разный цвет. Страны, у которых граница является точкой (или, если быть точнее, имеет нулевую длину), не считаются соседними. Ну и важно уточнить, что эксклавы (такие, как, например, Калининградская область) запрещены.
В 1879 году гипотезу доказал Альфред Кемпе, и его доказательству поверили, пока в 1890 году Перси Хивуд не нашел контрпример.
После этого гипотеза о четырех красках оставалась недоказанной вплоть до 1977 года, пока Кеннет Аппель и Вольфганг Хакен не представили свое доказательство. Это было первое в истории крупное математическое доказательство, полученное с помощью компьютера.
Всю эту историю я много раз слышал в научно-популярном изложении, но глубоко не вникал в математические детали. Помню только, что в курсе дискретной математики в университете, нам доказывали теорему о пяти красках.
Мне стало интересно разобраться, как именно доказывал эту теорему Кемпе, какой контрпример нашел Хивуд и как в итоге устроено компьютерное доказательство Аппеля и Хакена.
Я не нашел достаточно подробного изложения на русском языке, поэтому взял книгу Робина Уилсона «Four Color Suffice», узнал из нее все, что мне было интересно, и кратко пересказал это для вас. Большинство иллюстраций в статье взято из этой книги.
Приятного чтения!
Первое упоминание
23 октября 1852 года Огастес Де Морган, профессор математики Университетского колледжа в Лондоне, написал письмо своему другу сэру Уильяму Роуэну Гамильтону, выдающемуся ирландскому математику и физику. Конечно, никто из них и представить себе не мог, что содержание этого конкретного письма войдет в историю математики, поскольку именно в нем впервые была упомянута гипотеза о четырех красках.
Сегодня один мой студент попросил объяснить ему утверждение, о котором я ранее не знал и в верности которого до сих пор не уверен. Он говорит, что если фигура каким-либо образом разделена на части и эти части окрашены в разные цвета так, что фигуры, имеющие общую границу, окрашены в разный цвет – может потребоваться четыре цвета, но не более – в его случае требуется четыре цвета.
Вопрос: нельзя ли придумать пример, в котором возникнет необходимость в пяти или более цветах? Что вы скажете? И было ли это утверждение замечено ранее, если оно верно? Мой студент говорит, что догадался об этом, раскрашивая карту Англии…
Спустя годы студент, обратившийся к Де Моргану в тот роковой день, представился как Фредерик Гатри. Но оказалось, что это не Фредерик раскрашивал карту Англии и сформулировал гипотезу, а его брат Фрэнсис. Таким образом, считается, что именно Фрэнсис Гатри был первым, кто сформулировал гипотезу о четырех красках.
Задача о пяти принцах
На письмо Де Моргана Гамильтон ответил коротко:
Вряд ли я в ближайшее время смогу заняться вашей "четверкой" цветов.
Не растерявшись, Де Морган написал другим друзьям-математикам, пытаясь заинтересовать их этой проблемой. Он был очарован ее сложностью и в своем первоначальном письме Гамильтону попытался объяснить, в чем эта сложность заключается:
Насколько я вижу на данный момент, если есть четыре конечные области, и каждая из них имеет общую границу с каждой из трех других, то три из них охватывают четвертую и препятствуют появлению пятой связи с ней. Если это так, то четыре цвета раскрасят любую возможную карту без совпадения цветов на границах, за исключением точки.
То есть, кажется, что если нарисовать три области (A, B, C), любые две из которых имеют общую границу, вы не можете нарисовать четвертую область (D), которая граничит со всеми тремя, не "заперев" при этом одну из областей внутри. Но это сложное утверждение, и я не уверен во всех хитростях.
На самом деле здесь Де Морган ошибается. Из того факта, что одна из четырех областей всегда будет "заперта" вовсе не следует того факта, что четырех цветов будет достаточно для раскраски любой карты. Если бы первое утверждение было неверно, то из этого бы следовала неверность второго утверждения. Потому что неверность первого утверждения означала бы, что мы можем придумать пример, в котором есть пять областей, каждая из которых граничит с четырьмя другими. Из этого очевидно следует, что для их раскраски необходимо минимум пять цветов. Но если мы не можем придумать такого примера, это не значит, что четырех красок нам всегда хватит.
Задача о пяти областях, каждая из которых граничит с четырьмя другими, была известна еще до 1852 года. Около 1840 года ее задавал своим студентам Август Фердинанд Мебиус в следующей формулировке:
Жил-был в Индии царь, у которого было большое королевство и пятеро сыновей. В своем последнем завещании король указал, что после его смерти сыновья должны разделить королевство между собой таким образом, чтобы область, принадлежащая каждому сыну, имела общую границу (а не просто точку) со всеми остальными четырьмя областями. Как должно быть разделено королевство?
Интуитивно легко понять, почему задача Мебиуса, которую называют "Задачей о пяти принцах", не имеет решения. Предположим, что области, принадлежащие первым трем сыновьям, называются A, B и C. Все эти три области должны иметь общие границы друг с другом, как показано ниже на рисунке (а). Область D, принадлежащая четвертому сыну, теперь должна полностью находиться в пределах области, охватываемой областями A, B и C, или полностью за ее пределами: эти две ситуации показаны на рисунках (b) и (c). В каждой из этих ситуаций невозможно расположить область E, принадлежащую пятому сыну, таким образом, чтобы она имела границы с другими четырьмя областями - A, B, C и D:
Наблюдения Артура Кейли
После смерти Огастеса Де Моргана в 1871 году задача о четырех красках все еще оставалась нерешенной. И все же она не была полностью забыта: она продолжала занимать мысли, например, Артура Кейли из Кембриджского университета. 13 июня 1878 года он присутствовал на заседании Лондонского математического общества и поднял там вопрос о задаче четырех красок.
В апреле 1879 Артур Кейли опубликовал статью, в которой не привел доказательства, но сделал несколько полезных наблюдений. Например, он пишет:
Если система из n областей уже окрашена в четыре цвета и затем добавляется (n+1)-я область, то из этого никоим образом не следует, что мы можем раскрасить новую область теми же четырьмя цветами, не изменяя исходной окраски.
Например, пусть области, находящиеся на границе карты, раскрашены во все четыре цвета. Тогда если добавить новую область, которая окружает всю карту, для нее нет доступного цвета и требуется некоторая перекраска.
Еще Кейли обратил внимание на то, что доказывая достаточность четырех цветов для раскраски любой карты, мы можем наложить на карты более строгие условия. В частности, мы можем рассматривать только кубические карты, то есть карты, на которых в каждой точке пересечения границ находится не больше трех областей. Чтобы понять, почему это так, предположим, что в некоторых точках пересечения находится более трех областей. Над каждой такой точкой мы могли бы наклеить небольшую круглую “заплатку”, тем самым создав новую карту, на которой в каждой точке пересечения ровно три области. Если мы сможем раскрасить эту новую карту четырьмя цветами, как предполагалось, то мы легко получим раскраску нашей исходной карты, убрав «заплатки».
Аналогичным образом мы можем наложить другие ограничения. Например, как заметил Кейли, если мы можем раскрасить все карты в четыре цвета, то мы можем сделать это таким образом, чтобы на внешней границе карты находились только три цвета. Это связано с тем, что мы всегда можем добавить новую область в форме кольца, которое окружает карту. Раскрашивание этой новой карты четырьмя цветами сразу же дает нам раскраску исходной карты только с тремя цветами на внешней границе.
Формула Эйлера
В конце 1879 года, менее чем через год после статьи Кейли, Альфред Кемпе, лондонский адвокат и математик-любитель, опубликовал в American Journal of Mathematics свое «доказательство» гипотезы о четырех красках.
Начал он его со следующего наблюдения: если обозначить количество областей на карте за 
, количество граничных линий между областями за 
, количество точек пересечения граничных линий за 
, то всегда верна формула:
Эта формула очень похожа на формулу Эйлера для многогранников, которую Леонард Эйлер вывел в 1750 году, и которая может быть переформулирована для планарных графов. (На самом деле задача о четырех красках может быть переформулирована, как задача о раскраске вершин планарного графа, но мы не будем заострять на этом внимание в данной статье.)
Кемпе доказывал формулу следующим образом: возьмем произвольную карту и будем удалять с нее области по одной. Удалять область будем следующим образом: накроем эту область чистым листом бумаги (лоскутом) такой же формы, но немного большего размера, а затем расширим все границы, которые пересекаются с этим лоскутом, и соединим их в одной точке внутри лоскута, как показано ниже, что приведет к уменьшению области до точки.
При этом будем следить за тем, как изменяются на каждом шаге 
, 
и 
(обновленные значения обозначим за 
, 
и 
).
Если удаленная область была полностью вложена в другую область (например, была островом), то
, 
, 
.Если у удаленной области была одна граничная линия и одна граничная точка (например, область была полуостровом), то
, 
, 
.
Полуостров. Иллюстрация из статьи Кемпе Если у области было K граничных линий, то
, 
, 
. Это верно, даже если на границе удаленной области были точки пересечения, на которых пересекались более трех границ.
Иллюстрация из статьи Кемпе
Заметим, что на каждом шаге 
. В конце мы получим единственную область, для которой значение 
. Поскольку это выражение остается неизменным на протяжении всего процесса, мы делаем вывод, что 
равно 
для исходной карты. Это доказывает верность аналога формулы Эйлера для карт.
Теорема о пяти соседях
Важным следствием из формулы Эйлера является теорема о пяти соседях:
На каждой карте есть по крайней мере одна область с пятью или менее соседями.
Этот результат очень важен – он занимает центральное место в любом доказательстве теоремы о четырех красках.
Чтобы доказать эту теорему, заметим, что в каждой точке пересечения пересекаются как минимум три граничные линии. Если бы в точке пересечения было только две граничные линии, то мы могли бы просто удалить точку, не влияя на цветовую гамму.
Теперь посчитаем граничные линии, исходящие из всех этих точек пересечения. Получается, что в общей сложности у нас будет не менее 
граничных линий, потому что у каждой из 
точек пересечения есть по крайней мере три граничные линии. Но каждая граничная линия имеет точки пересечения на каждом конце и поэтому учитывается дважды, поэтому мы должны разделить результат на 
. Таким образом, 
, или 
.
Докажем теорему о пяти соседях от противного. Предположим, что каждая область окружена по крайней мере шестью соседями. Таким образом, при подсчете пограничных линий вокруг всех областей мы получаем в общей сложности не менее 
пограничных линий, потому что каждая из областей 
окружена по меньшей мере шестью пограничными линиями. Но опять же, каждая линия была подсчитана дважды, потому что с каждой стороны от нее есть область, поэтому мы должны разделить результат на 
. Таким образом, 
равно, по меньшей мере, 
(
), что мы можем переписать как 
.
Теперь мы подставим эти два неравенства 
и 
в аналог формулы Эйлера и получим 
, что равно 
. Но по формуле 
равно 
. Противоречие возникло из-за того, что мы предположили, что у каждой области есть по крайней мере шесть соседей, поэтому это предположение неверно. Из этого следует, что по крайней мере у одной области пять или меньше соседей, что и требовалось доказать.
Алгоритм Кемпе
Доказав теорему о пяти соседях, Кемпе описал метод раскрашивания любой карты в четыре цвета. Его можно свести к пяти шагам:
Найдите область с пятью или меньшим количеством соседей (согласно теореме о пяти соседях, такая область существует).
Удалите эту область, схлопнув ее до точки (тем же способом, который был использован в доказательстве формулы Эйлера).
Повторяйте первые два шага до тех пор, пока не останется только одна область.
Раскрасьте единственную оставшуюся область любым из четырех цветов.
Восстанавливайте области в обратном порядке. На каждом шаге у восстановленной области будет не более пяти соседей. Раскрасьте ее любым доступным цветом, пока вся карта не будет окрашена в четыре цвета.
На последнем шаге возникает проблема: как мы всегда можем быть уверены, что при восстановлении области будет доступен один из четырех цветов? Нет никаких трудностей, если наша восстановленная область имеет не более трех граничных линий. Например, если это треугольная область, то она окружена тремя областями, которые раскрашены всего тремя цветами; тогда для раскрашивания треугольника доступен четвертый цвет, как показано ниже.
Но что мы будем делать, если наша восстановленная область будет иметь четыре или пять границ? В таком случае она может быть окружена областями, окрашенными всеми четырьмя цветами, как показано ниже. В таком случае нет доступного цвета для раскрашивания четырехугольника или пятиугольника.
Цепочки Кемпе
Чтобы преодолеть эту трудность, Кемпе ввел метод, который теперь известен как метод "цепочек Кемпе". В этом методе мы смотрим на области, окружающие восстановленную, и выбираем две из них, которые не являются смежными и при этом окрашены в разный цвет — скажем, красную и зеленую. Затем мы смотрим только на те области, которые окрашены этими цветами.
Мы проиллюстрируем метод Кемпе, сначала показав, как он поступил с четырехугольником (который мы обозначим за S), окруженным четырьмя областями разного цвета. Сначала мы посмотрим на красных и зеленых соседей четырехугольника S. Каждый из них является отправной точкой для красно-зеленой части карты, то есть части карты, полностью состоящей из областей, окрашенных в красный или зеленый цвета.
Хотя они и называются цепочками Кемпе, эти двухцветные участки карты обычно не являются цепочками и могут содержать "ветвления", как показано на приведенных ниже рисунках. Эти ветвления могут содержать произвольное расположение областей. До тех пор, пока они окрашены правильным образом, их форма не имеет никакого отношения к проблеме окрашивания S.
Теперь зададимся вопросом, отделены ли эти две красно-зеленые части друг от друга или они связаны? Могут возникнуть две ситуации:
Случай 1.
Здесь красные и зеленые области, находящиеся выше S, не связаны с красными и зелеными областями, находящимися ниже S. Таким образом, мы можем поменять местами цвета красных и зеленых областей над S, как показано ниже, не затрагивая цвета красных и зеленых областей под S. В этом случае четырехугольник S будет окружен только зелеными, синими и желтыми цветами, так что S может быть окрашен в красный цвет. На этом раскраска карты завершается.
Случай 2.
Здесь красно-зеленая часть над S соединяется с красно-зеленой частью под S. Это немного усложняет задачу, поскольку замена красного и зеленого цветов ничего не дает: красный сосед S становится зеленым, а зеленый сосед S становится красным, и мы оказываемся в том же положении, что и раньше. Вместо этого мы обращаем наше внимание на синюю и желтую области и на сине-желтые участки карты слева и справа от квадрата S. Здесь сине-желтая часть справа от S отделена от сине-желтой части слева от S, потому что цепочка из красных и зеленых областей встает у нее на пути. Таким образом, мы можем поменять местами цвета синей и желтой областей справа от S, не затрагивая цвета синей и желтой областей слева от S. Тогда четырехугольник S будет окружен только желтыми, красными и зелеными цветами, так что S может быть окрашен в синий цвет.
Затем Кемпе рассмотрел случай, когда восстановленная страна представляет собой пятиугольник (который мы обозначаем буквой P), окруженный пятью странами, окрашенными в четыре разных цвета. (Как будет показано далее, именно эта часть доказательства содержит фундаментальную ошибку.)
Заметим, что один из цветов будет повторяться дважды (в нашем случае это синий).
Кемпе выбрал два неповторяющихся цвета, которые не являются смежными. Сначала он рассмотрел желто-красные области над и под буквой P. Если желто-красная часть над P не связана с желто-красной частью под P, то мы можем поменять местами цвета желтых и красных стран над P, не влияя на окраску стран под P. После этого P можно окрасить в желтый цвет.
Далее, рассмотрим случай, когда красно-желтая часть над P соединяется с красно-желтой частью под P.
В этом случае Кемпе рассматривал зелено-красные области выше и ниже P. Если зелено-красная часть над P не совпадает с зелено-красной частью под P, то мы можем поменять местами цвета зеленых и красных стран над P, не влияя на окраску стран под P. После этого P может быть раскрашен в зеленый цвет.
Таким образом, остается случай, когда зелено-красная часть над P соединяется с зелено-красной частью под P. Объединяя это с предыдущим случаем, мы получаем:
Заметим, что сине-желтая часть справа от P отделена от сине-желтой части слева от P, потому что ей мешает красно-зеленая цепочка стран. Таким образом, мы можем менять местами цвета сине-желтой части справа от P, не влияя на окраску сине-желтой части слева от P.
Аналогично, сине-зеленая часть слева от P отделена от сине-зеленой части справа от P, потому что на пути возникает красно-желтая цепочка стран. Таким образом, мы можем менять местами цвета сине-зеленой части слева от P, не влияя на окраску сине-зеленой части справа от P.
Если мы выполним обе эти замены, то пятиугольник P будет окружен только желтым, красным и зеленым цветами, и P может быть окрашен в синий цвет.
Поскольку мы рассмотрели все возможные случаи, теорема о четырех красках доказана.
Послесловие к первой части
Спасибо, что дочитали до конца первую часть. В следующей части я продемонстрирую контрпример, который нашел Перси Хивуд и который опровергает доказательство Альфреда Кемпе, и продолжу рассказывать историю доказательства теоремы о четырех красках.
А пока что можете попробовать найти контпример сами. Сразу скажу, что задача эта совсем нетривиальная. Математикам 19-го века потребовалось 11 лет, чтобы это сделать, а до этого момента доказательство Кемпе пользовалось большим признанием, а сам Кемпе был даже принят в члены Королевского общества.
Удачи и до встречи!