Жемчужина Эйлера полностью

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

Ошибка атрибуции проистекает из истории, рассказанной одним из студентов Мёбиуса Ричардом Бальцером (1818–1887). Бальцер писал, что в 1840 г. Мёбиус поставил перед аудиторией проблему пяти принцев. Он описал ее следующим образом:

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

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

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

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

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

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

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

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

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

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