Количество красок, требуемых для раскраски карты

Всем известно, географические карты печатаются в несколько красок, лучше всего каждую страну печатать разным цветом. Но так как многоцветное печатание чрезвычайно дорого, раскрашивая карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, которые примыкают одна к другой вдоль какой-либо границы, были окрашены по-разному. И тут появляется вопрос: а какое количество красок достаточно, чтобы закрасить любую карту? В 1852 году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. А Кэли поставил в 1979 г. данную задачу в Лондонском географическом обществе.

Географическая карта острова, показанного на рис. 1, а, требует при этих условиях трех красок: море, как обычно, закрашивается синей краской, и две другие краски используются для двух стран. На рис. 1, б показана карта, безусловно требующая четырех красок, ибо здесь все три страны примыкают к морю, и потому ни одна из них не может быть окрашена в тот же цвет, что и море; а поскольку каждая из них соприкасается с двумя другими, все три должны получить разные окраски.

Карта, схематически изображенная на рис. 1, в, требует также четырех красок, если даже мы не учтем море: средняя страна играет здесь ту же самую роль, какую на рис. 1, б играло море.

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

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

В 1977 году доказательство гипотезы четырех красок было, наконец, получено К. Аппелем и У. Хакеном. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого скептицизма по отношению к данному доказательству. Сначала мы приведем точные формулировки и докажем теорему о пяти красках.

Проблемы раскраски карты на глобусе и плоскости эквивалентны. Действительно, в случае карты на сфере можно вырезать кусок внутренней области какой-либо страны; продырявленную сферу можно деформировать в плоскую область – представим, что карта сделана из тонкой резины.

На плоской карте отверстие превратится в "океан", омывающий со всех сторон одну страну. Разумеется, длины границ, их форма, размеры стран подвергнутся при растяжении значительным изменениям, но сетка границ останется, добавится лишь растянутая граница прорезанного отверстия, внешняя граница океана. Ее можно убрать, то есть раскрасить океан так же, как и окруженную им страну. Такие деформации стран и их границ, очевидно, не меняют задачи раскраски. Ниже рассматривается плоская карта.

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

Определение 1. Графом G называется конечное множество вершин V(G) и конечное множество ребер R(G), так что каждое ребро имеет своими концами две различные вершины. Граф называется плоским, если вершины являются точками плоскости, а ребра – ломаными линиями (составленными из отрезков) в этой же плоскости, имеющими своими концами вершины, не пересекающимися между собой и не включающими других вершин, кроме своих концов.

Отметим, что в плоском графе не допускаются петли (ребра, имеющие началом и концом одну и ту же вершину).

Плоский граф разрезает плоскость на совокупность D(G) неперекрывающихся многоугольных областей, необязательно конечных (рис. 4).

Если перенумеровать используемые краски 1, 2, ..., n, то на соответствующем карте плоском графе этими числами окажутся занумерованы вершины (столицы).

Определение 2. Правильной n-раскраской плоского графа G называется отображение : , причем, в случае, если существует такое ребро , что граница состоит из и .

Наконец, можно сформулировать проблему четырех красок в виде следующего утверждения.

Теорема 1. Любой плоский граф допускает правильную 4-раскраску.

Вот решение этой-то проблемы и заняло более столетия. Однако на первый взгляд чуть более слабое утверждение о правильной 5-раскраске доказать достаточно просто. Для доказательства понадобится формула Эйлера, связывающая число вершин, ребер и областей. Пусть обозначает число элементов конечного множества M.

Теорема Эйлера. Для любого плоского графа .

Теорема 2. Любой плоский граф допускает правильную 5-раскраску.

Доказательство. Сначала упростим граф. Если есть несколько ребер, соединяющих некоторую пару вершин (такая ситуация может возникнуть, если две страны имеют несколько несвязанных между собой кусков границы, например как у России и Китая), то оставим только одно ребро: правильность раскраски такого уменьшенного графа все равно гарантирует правильную раскраску исходного.

Проведем теперь индукцию по числу вершин графа. Для графа с тремя вершинами утверждение теоремы очевидно. Пусть оно справедливо для всех графов с вершиной.

Пусть – полный набор всех областей графа, а – число ребер, составляющих границу -й области графа. При этом для любого . Любое ребро входит в границу в точности двух областей, поэтому

.

Вследствие неравенств имеем

, откуда .

По формуле Эйлера , откуда

и, следовательно,

(1)

Заметим, что удвоенное число ребер можно отождествить и с другой характеристикой графа. Пусть есть полный набор вершин графа, а – число ребер, сходящихся в вершине с номером . Но каждое ребро заканчивается двумя вершинами, поэтому

.

Кроме того, как это следует из неравенства (1), .

Следовательно,

(2)

Из последнего неравенства можно вывести, что существует, по крайней мере, одна вершина, в которой сходится не более пяти ребер. Действительно, предположим противное, то есть . Тогда , что противоречит (2).

Перенумеруем вершины так, что в вершине сходится не более пяти ребер.

Если в вершине сходятся не более четырех ребер, то рассмотрим граф , который получается из устранением вершины и всех оканчивающихся в ней ребер. Граф допускает правильную 5-раскраску по предположению индукции. А так как ребра соединяют вершину, а не более чем с четырьмя вершинами этого меньшего графа, то для правильной раскраски остается, по крайней мере, один цвет (из пяти).

Пусть теперь в сходится ровно пять ребер. Рассмотрим граф , состоящий из тех пяти вершин, куда приходят ребра, выходящие из и соединяющих их (в ) ребер. В графе обязательно найдутся две вершины, не соединенные ребром. Действительно в противном случае в пятиугольнике будет ребер (это нетрудно посчитать и непосредственно). Однако, в силу (1)

,

и мы приходим к противоречию.

Пусть и суть те вершины , которые не соединены между собой. Не соединены они и в . Рассмотрим граф , который получается из при помощи деформации, которая отождествляет и .

Граф – это плоский граф, так как при отождествлении вершин в этой ситуации не может возникнуть петли. Но для справедливо предположение индукции, и существует некоторая его правильная 5-раскраска . Разъединим в этом раскрашенном графе вершины и . Тогда правильную 5-раскраску получает и граф , причем такую, что . Иными словами, и раскрашены одинаково и, следовательно, раскраска пяти соседних с вершин графа использует не более четырех цветов.

Используем оставшийся цвет для раскраски вершины и получим правильную 5-раскраску .

Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более 20 ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования. И это тоже характерно для математики: решение задачи, изучаемой из чистого любопытства, оказывается полезным в описании реальных и совершенно различных по своей природе объектов и процессов.

О доказательстве теоремы четырех красок.

Доказательство К. Аппеля и У. Хакена, в целом, хотя и принятое математическим сообществом, вызывает до сих пор определенный скептицизм. Для читателя, поверхностно знакомого с математикой, предыдущая фраза должна вызвать изумление: а как же обязательный для математики принцип исключенного третьего, в соответствии с которым утверждение либо справедливо, либо нет? Дело обстоит не так просто. Вот что пишут сами авторы доказательства: «Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно».

Говоря прямо, компьютерную часть доказательства невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Между тем доказательство, не поддающееся проверке, есть нонсенс. Согласиться с подобным доказательством означает примерно то же, что просто поверить авторам. Но и здесь все сложнее.

Долгое время идеалом математической строгости были формулировки и доказательства Евклида, в которых осуществлялась программа вывода теорем из аксиом по определенным правилам (метод дедукции, позволяющий получать неочевидные утверждения из очевидных). Этот образец строгости и в наше время недостижим в курсе школьной математики, но для современной чистой математики стандарты Евклида недостаточны. Евклид, по-видимому, не задумывался над тем, почему прямая делит плоскость на две части (и что это значит), он не определял понятия "между", считая это понятие очевидным и т.д. Большая часть соответствующих утверждений доказана или включена в аксиоматику геометрии только в последнюю сотню лет. Формальные выводы из новой системы аксиом стали гораздо длиннее, чем в античные времена.

Трудно даже вообразить длину полного вывода теоремы о пяти красках в соответствии с современными стандартами математической логики и системы аксиом геометрии. Но совершенно точно, что такое рассуждение никто никогда не проделывал из-за бесполезности этого занятия: формальные выводы практически не поддаются проверке в силу свойств человеческой психики: помимо их гораздо большей длины их сознательное усвоение идет гораздо медленнее. Поэтому обычно удовлетворяются уверенностью в том, что формальный вывод возможен в принципе.

Таким образом, вопрос о доказательстве теоремы четырех красок с точки зрения чистой математики остается открытым.

ЛИТЕРАТУРА

1. Радемахер Г., Теплиц О. Числа и фигуры. Опыты математического мышления. - М.: «Наука», 1966. - 264 с.

2. Самохин А.В. Проблема четырех красок: неоконченная история доказательства// СОЖ, 2000, №7, с. 91-96.