Жемчужина Эйлера - Дэвид С. Ричесон

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

На следующий день Мёбиус признался студентам, что в таком виде задача неразрешима.

Рис. 14.3. Август Мёбиус

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

В постскриптуме Бальцер пришел к неверному выводу, будто неразрешимость этой задачи означает, что теорема о четырех красках верна. Он писал: «С каким восторгом Мёбиус, должно быть, видел далеко идущие применения» этой задачи117. Тонкая связь между проблемой пяти принцев и проблемой четырех красок заключается в том, что если бы нужное разделение царства существовало, то его карту (подобно карте на рис. 14.2) было бы невозможно раскрасить только лишь четырьмя цветами. Однако на самом деле это устраняет лишь одно препятствие к доказательству теоремы о четырех красках. Остается теоретическая возможность построить сложную карту, в которой нет пяти взаимно граничащих областей, но тем не менее раскрасить ее четырьмя цветами невозможно. По словам Мартина Гарднера, многие неправильные доказательства теоремы о четырех красках, ложившиеся в его почтовый ящик, на самом деле были не чем иным, как замаскированной проблемой пяти принцев.

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

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

Рис. 14.4. Граф смежности карты

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

Гипотеза четырех красок для планарных графов

Любой простой планарный граф допускает 4-раскраску.

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

Рис. 14.5. Раскраска графа смежности порождает раскраску карты

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

Теорема о пяти соседях

В каждом простом планарном графе существует вершина степени 5 или меньше.

Пусть имеется простой планарный граф. Поскольку в нем нет петель и параллельных ребер, можно добавить ребра так, что каждая грань будет ограничена ровно тремя ребрами. Мы докажем, что этот (больший) триангулированный граф содержит вершину степени 5 или меньше, а потому такая вершина должна быть и в (меньшем) исходном графе. Предположим, что триангулированный граф имеет V вершин, E ребер и F граней (внешняя область считается гранью). Каждое ребро является общей границей двух граней, а каждая грань ограничена тремя ребрами, поэтому 3F = 2E. По формуле Эйлера, V — E + F = 2, или, эквивалентно, 6E — 6F = 6V — 12. Подставляя 4E вместо 6F, получаем

2E = 6V — 12.

Поскольку у каждого ребра два конца, сумма степеней всех вершин равна 2E. Поэтому средняя степень вершин равна

Так как средняя степень меньше шести, то должна существовать по меньшей мере одна вершина степени 5 или меньше.

Чтобы продемонстрировать полезность теоремы о пяти соседях в задачах раскрашивания графов, докажем теорему о шести красках.

Теорема о шести красках

Любую карту можно раскрасить шестью или меньшим количеством цветов.

Предположим, что это утверждение неверно. Тогда найдется одна или несколько карт, которые нельзя раскрасить шестью цветами. Найдем в этом множестве «плохих» карт карту с наименьшим числом стран. Пусть число стран на этой карте равно N. Такой наименьший контпример часто называют минимальным злодеем. Польза выделения минимального злодея в том, что можно с уверенностью сказать, что любую карту, содержащую N — 1 или меньше стран, можно раскрасить шестью цветами.

Рассмотрим граф смежности G минимального злодея. По теореме о пяти соседях, в G найдется вершина v степени 5 или меньше. После удаления v и всех инцидентных ей ребер из G получится новый граф H. Легко видеть, что H является графом смежности карты с N — 1 странами. Поскольку H содержит N — 1 вершин, его можно раскрасить шестью цветами. Теперь вернем удаленную вершину вместе с ребрами в граф. Поскольку v соседствует не более чем с 5 другими вершинами, найдется хотя бы один неиспользованный цвет, которым можно покрасить v. Таким образом, G можно раскрасить в шесть цветов. Это противоречит предположению о том, что G — минимальный злодей, а следовательно, любая карта допускает 6-раскраску. На рис. 14.6 эта техника использована для раскрашивания графа в красный, синий, зеленый, фиолетовый