Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.5. Раскраска графов и вопросы топологии

Задача о раскраске карты

Удивительный факт: любую политическую карту можно раскрасить всего четырьмя красками, причем так, что соседние страны на ней не будут окрашены в один цвет. Пронумеруем краски: 1 — красная, 2 — зеленая, 3 — синяя и 4 — желтая. Пусть рис. 3.67 изображает гипотетический континент, омываемый со всех сторон океаном и разделенный прямолинейными границами на суверенные государства. Единственное условие этой карты такое: все страны должны иметь друг с другом протяженные границы, т.е. они не могут соприкасаться в единственной точке, что представляется вполне разумным. Действительно, так не бывает, чтобы реальные страны соприкасались в одной-единственной идеально геометрической точке. Ведь нужно же куда-то вкопать пограничный столб, поставить шлагбаум, определить местоположение будки для пограничника. Значит, должна быть минимальная протяженность границы между странами, иначе теряет смысл само слово граница. Если это реалистическое требование выполняется, то во всех узловых точках соприкасаются по три страны, т.е. регулярный граф, образованный линиями границ, имеет вершины третьей и только третьей степени.

Рис. 3.67

Нашу гипотетическую карту начнем раскрашивать следующим образом. Океан можно принять за некую «страну рыб и водорослей», которую закрасим в синий цвет (3). Поэтому все прибрежные страны уже нельзя будет закрашивать этой краской, в противном случае нарушится принцип запрета на соседство двух одинаковых красок. Далее выберем любую, первую попавшуюся страну и назначим ей цвет 1 (на рис. 3.67 эта страна обозначена серым цветом). Две ее соседки с выходом к морю окрасим в зеленый цвет 2. Далее идем по часовой стрелке и окрашиваем подряд все прибрежные страны так, что у нас получится цепочка: 1 – 2 – 1 – 2 – 4 – 1 – 2 – 1 – 2. Желтый (4) цвет здесь появился потому, что красным цветом (1) мы не имели права пользоваться в силу ограничивающего условия. Затем начинаем раскрашивать четыре внутриконтинентальные страны, которые имеют огромные города-столицы (они обозначены белыми кружками) с отходящими от них во все страны-соседки шоссейными магистралями (они обозначены пунктирными прямыми). Пусть цвет страны совпадает с названием страны и названием столицы, т.е. в центральной части континента располагаются Красная (1), Зеленая (2), Синяя (3) и Желтая страны и, соответственно, столицы.

Дальнейшая закраска карты не вызовет проблем до тех пор, пока мы не дойдем до самой последней страны. Чаще всего получается так, что для нее выбор из четырех красок оказывается недостаточным, так как все ее соседки уже раскрашены в четыре цвета. Чтобы не нарушать исходного условия, нам придется взяться за перекраску однажды уже окрашенных стран; в этом как раз и состоит проблема четырех красок. Дело в том, что процедура перекраски может затянуться и мы вынуждены будем перекрашивать еще одну страну, потом еще и т.д. Однако геометрам всегда удавалось за конечное число перекрасок прийти в полное согласие с условием. Им не попадалось такой карты, сколько бы в ней ни было стран, чтобы ее нельзя было покрасить четырьмя красками. Это выглядит несколько странно, что привело к формулировке задачи, которая, наподобие Великой теоремы Ферма, не была решена на протяжении столетия.

Задача формулируется так: действительно ли четырех красок достаточно для раскраски произвольно взятой политической карты с протяженными границами, чтобы две любые соседние страны были окрашены в различные цвета? Иногда в математической литературе эту задачу формулируют несколько иначе. Пусть регулярный граф границ имеет в местах соединения трех границ особые пункты (два таких пограничных пункта внутри двух дорожных треугольников помечены темными кружками). Как можно заметить по нашему рис. 3.67, граф дорог и граф границ образуют взаимно двойственные графы. Отсюда появляется возможность новой формулировки проблемы: возможно ли с помощью четырех красок раскрасить вершины двойственного графа, построенного на карте с протяженными границами таким образом, чтобы любые две его соседние вершины имели различные цвета?

Этой проблемой был озабочен немецкий математик Август Фердинанд Мёбиус (1790—1868) — родоначальник науки топологии, которая в дальнейшем нас будет особенно интересовать. Его имя прославила так называемая петля Мёбиуса — узкая полоска бумаги, закрученная и склеенная так, как показано на рис. 3.68. Она имеет неориентированную поверхность. Дело в том, что если вы начнете по ней путешествовать от точки Q и сделаете полный оборот в 360 градусов, то вы не придете в то же самое место, а окажитесь с другой стороны ленты, в точке Q', хотя ваша дорога нигде не прерывалась. Изучением столь странных свойств поверхностей как раз и занялась наука топология (topoz — место), целью которой является исследование свойств непрерывности различных поверхностей. Мёбиус был разносторонним ученым; долгое время он работал в Лейпцигской астрономической обсерватории и немало времени посвятил разработке координатных сеток для карт звездного неба. Известно, что около 1840 г. он размышлял над задачей о четырех красках, о которой он говорил как об известном любопытном факте.

Рис. 3.68

Дальнейшая судьба этой задачи такова. В первом томе Трудов Лондонского географического общества 1879 г. известный британский алгебраист Артур Кэли (1821—1895) поместил статью, где отчетливо сформулировал задачу о четырех красках, которая до этого была известна как занятная головоломка. В то время он занимался метрической геометрией и теорией инвариантов непрерывных точечных преобразований, которые входили тогда в качестве раздела в молодую науку топологию. Уже через год ее решение представил А. Кемпе, но, как потом оказалось, он поспешил. Его доказательство раскритиковал Р. Хивуд, который в 1890 г. в работе «Теоремы о раскраске карты» показал, что задачу можно решить точно, если иметь в своем распоряжении не четыре, а пять красок. После этих попыток задачу надолго отложили и только в 1969 г. к ней вернулся математик Х. Хееш, показавший, что она сводится к проблеме неприводимых конфигураций.

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