Жемчужина Эйлера

Глава 11 Прогулка по Кёнигсбергу

Чтобы поместить формулу Эйлера в современный контекст, нам придется обсудить раздел математики, называемый теорией графов. Речь идет не о графиках функций, с которыми мы знакомились в школе на уроках алгебры и основ математического анализа (y = mx + b — прямая, y = x² — парабола и т. д.), а об изучении объектов — графов, — показанных на рис. 11.1. Они состоят из точек, называемых вершинами, и соединяющих эти точки линий, называемых ребрами[7].

Рис. 11.1. Графы

В 1736-м, во время своего первого пребывания в Санкт-Петербурге, Эйлер занялся знаменитой задачей о семи кёнигсбергских мостах. Его вклад в решение этой задачи часто называют рождением теории графов и топологии.

Город Кёнигсберг был основан тевтонскими рыцарями в 1254 году. В то время он находился в Пруссии, недалеко от Балтийского моря, в развилке реки Прегель. Впоследствии он стал столицей Восточной Пруссии. Город, сильно пострадавший от бомбежек союзников во время Второй мировой войны, был передан Советскому Союзу по условиям Потсдамской конференции. После того как Кёнигсберг стал частью Советского государства, там произошло много изменений — большая часть коренных немецких жителей была выселена, город был переименован в Калининград, а река получила название Преголя. Сегодня Калининград — часть России и столица Калининградской области. Особенность Калининградской области состоит в том, что она не связана с остальной Россией, а окружена Польшей, Литвой и Балтийским морем. В отличие от таких городов, как Сталинград и Ленинград, Калининграду не было возвращено его прежнее название. Самым знаменитым жителем Кёнигсберга был философ XVIII века Иммануил Кант (1724–1804). Из Кёнигсберга также родом Христиан Гольдбах — математик, которому Эйлер сообщил об открытии формулы для многогранников.

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

Неизвестно, как Эйлер узнал об этой задаче. Быть может, он услыхал о ней от своего друга Карла Элера, мэра прусского города Данцига, который переписывался с Эйлером от имени местного профессора математики. У нас имеются письма Эйлера и Элера за период с 1735 по 1742 год, и в некоторых из них обсуждается задача о кёнигсбергских мостах. Мы знаем, что поначалу Эйлер ей не заинтересовался. В 1736 г. в письме к Элеру Эйлер пишет:

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

Рис. 11.2. Семь кёнигсбергских мостов

В другом письме, датированном 1736 годом, к итальянскому математику Джованни Маринони (1670–1755) Эйлер писал:

В этом письме Эйлер употребил предложенный Лейбницем термин geometriam situs, или «геометрия положения». Позже он превратился в analysis situs (анализ положения) и, наконец, в топологию. Лейбниц имел в виду новый раздел математики, в котором «изучалось положение, как алгебра изучает величины»⁸⁷. Среди ученых нет согласия по вопросу о том, правильно ли Эйлер понял, что разумел Лейбниц под этим термином; тем не менее Эйлер был согласен с Лейбницем, что для изучения этой ситуации необходим новый математический подход.

В 1736 году Эйлер представил Санкт-Петербургской академии статью «Solutio problematis ad geometriam situs pertinentis» («Решение задачи, относящейся к геометрии положения»)⁸⁸, опубликованную в 1741 году. В ней он решил задачу о кёнигсбергских мостах и в свойственной ему манере обобщил решение на любое расположение мостов.

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

Рис. 11.3. Граф, ассоциированный с задачей о кёнигсбергских мостах

Таким образом, задача свелась к задаче о графе — можно ли начертить этот граф, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру? Глядя на пример, мы можем сформулировать более общий вопрос: как узнать, можно ли начертить заданный граф таким образом?

Часто думают, что граф кёнигсбергских мостов, показанный на рис. 11.3, приведен в статье Эйлера. Это ошибка — там нет ни кёнигсбергского, ни какого другого графа. Принципы вычерчивания графов развивались независимо от задачи о кёнигсбергских мостах. Головоломки на эту тему появились в начале XIX века как в математических статьях, так и в книгах по развлекательной математике. И лишь в 1892 году У. У. Роуз Болл (1850–1925) в своей популярной книге «Математические задачи и развлечения»⁸⁹установил связь между результатом Эйлера о кёнигсбергских мостах и вычерчиванием графов. Впервые кёнигсбергский граф появился в книге Болла спустя сто пятьдесят с лишним лет после публикации статьи Эйлера.

Также статью Эйлера часто называют зарождением теории графов. Это утверждение не лишено оснований. Хотя Эйлер не чертил графов в своей статье, его абстрактный подход к проблеме напоминает рассуждения, свойственные теории графов. Его применение новой дисциплины — geometriam situs, или топологии, — к задаче и осознание новизны этого метода свидетельствуют об основании нового раздела математики.

Для обсуждения решения нам понадобится несколько определений. Как и в случае многогранников, будем называть степенью вершины количество исходящих из нее ребер. Если в вершине есть петля (ребро, начинающееся и заканчивающееся в ней, как в правом графе на рис. 11.1), то она увеличивает степень на 2. В графе, образованном кёнигсбергскими мостами, имеется три вершины степени 3 и одна вершина степени 5. Граф называется связным, если из любой вершины можно дойти до любой другой, следуя по ребрам.

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

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

Эйлер решил обе эти задачи. В переводе на современный язык решение описывается следующим образом.

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

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

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

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

Обратное утверждение Эйлер принял как само собой разумеющееся: если в графе имеется ноль или две вершины нечетной степени, то он допускает эйлеров обход. Первое доказательство этого факта было дано Карлом Хирхольцером (1840–1871) и опубликовано после его смерти, в 1873 году⁹⁰.

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

Если этот путь не проходит по всем ребрам графа, то удалим все посещенные ребра и посмотрим на оставшийся граф (возможно, он уже не связный). Поместим карандаш в какую-нибудь вершину, которая посещалась при первоначальном вычерчивании. Как и раньше, будем вычерчивать граф, пока не окажется, что дальше двигаться невозможно. В нашем примере получится обход jkl. Теперь вставим новую трассу вычерчивания в нужное место построенного ранее обхода. В нашем примере путь jkl вставляется между ребрами b и c первоначального обхода. Таким образом, мы получили путь abjklcdefghi, являющийся эйлеровым обходом. В общем случае, возможно, придется проделать такую вставку несколько раз, пока не будут вычерчены все ребра.

Рис. 11.4. Построение эйлерова обхода

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

В 1875 году, спустя полтора века после того, как Эйлер проанализировал маршруты прогулок по Кёнигсбергу, в городе был построен новый мост⁹¹. Он был возведен к западу от острова Кнайпхоф и соединил северный берег реки с южным (рис. 11.5). Наконец-то жители Кёнигсберга смогли совершить прогулку по всем мостам, пройдя по каждому ровно один раз, поскольку теперь оказалось ровно две вершины нечетной степени — соответствующие острову и суше между рукавами реки. Конечно, некоторые горожане не могли начать прогулку от порога своего дома, и никому не удалось бы закончить прогулку в том же месте, где она началась.

Рис. 11.5. Новый мост в Кёнигсберге и новый граф

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

В заключение приведем три примера. В 1847 году Иоганн Бенедикт Листинг (1808–1882), математик, с которым мы еще встретимся снова, придумал граф, изображенный на рис. 11.6, чтобы проиллюстрировать проблему вычерчивания (мы рисуем граф так, как это сделал Листинг, опуская вершины в точках пересечения)⁹². Допускает ли этот граф эйлеров обход? А эйлеров цикл? Предлагаем читателю подумать над этой задачей, прежде чем продолжить чтение.

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

Рис. 11.6. Головоломка Листинга на вычерчивание графа

Второй пример — вариация на тему задачи о мостах. Рассмотрим рисунок, напоминающий кирпичную стену (рис. 11.7). Можно ли провести непрерывную кривую, пересекающую каждый отрезок ровно один раз (кривая может начинаться и заканчиваться в разных кирпичах)? Попытка, показанная на правом рисунке, — не решение, потому что кривая не пересекает один отрезок.

Рис. 11.7. Неправильное решение головоломки

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

И наконец, применим теорию графов и эйлеровых обходов к игре в домино. Этот пример придумал Орли Теркем (1782–1862) в 1849 году⁹³. В стандартном комплекте домино на каждой половине костяшки нанесено от одной до шести точек. В комплекте нет двух одинаковых костяшек и все комбинации присутствуют. Всего, таким образом, получается 28 костяшек. Каждый игрок по очереди выкладывает костяшки, так чтобы число точек на одной половине его костяшки совпадало с числом точек на свободном конце уже выложенной костяшки. Костяшки с одинаковым числом точек на обеих половинах (дубли) можно класть перпендикулярно костяшке с соответствующим числом точек (как на рис. 11.9). Игра заканчивается, когда игрок не может выложить очередную костяшку. Спрашивается, всегда ли игра заканчивается, когда у какого-то игрока на руках есть костяшки? Или можно выложить все костяшки, так что у игроков ни одной не останется?

Рис. 11.8. Граф, ассоциированный с головоломкой о кирпичной стене

Рис. 11.9. Типичная партия в домино

Для анализа этой задачи построим граф следующим образом. Начнем с семи вершин, пронумерованных от 0 до 6. Каждой костяшке соответствует ребро графа. Костяшке с m точками на одной половине и n точками на другой соответствует ребро из вершины m в вершину n. Сопоставив ребра всем костяшкам, мы получим граф, показанный на рис. 11.10. Заметим, что в каждой вершине имеется петля, соответствующая костяшкам-дублям.

Все вершины в графе домино имеют степень 8. Поскольку степени всех вершин четные, граф допускает эйлеров обход. Следовательно, весь граф можно вычертить, не проходя по одному ребру дважды. Это наблюдение и есть ключ к ответу на поставленный вопрос. Чтобы показать, что можно сыграть все костяшки домино, достаточно предъявить соответствующую партию. Мы построим ее просто (хотя вряд ли такая конфигурация возникнет в реальной партии) — выстроив костяшки в линию.

Рис. 11.10. Граф, соответствующий комплекту костяшек домино

Начнем с первого ребра в эйлеровом обходе. Пусть оно соединяет вершины 0 и 3. Выложим костяшку, содержащую 0 и 3 точки (0:3). Теперь рассмотрим второе ребро в обходе. Допустим, что оно соединяет вершины 3 и 1. Выложим костяшку 3:1, приложим ее к предыдущей (рис. 11.11). Будем продолжать таким же образом, выкладывая костяшки на каждом шаге. Поскольку мы совершаем эйлеров обход, каждое ребро будет посещено ровно один раз. Поэтому мы сможем выложить все до одной костяшки.

Рис. 11.11. Часть партии в домино и соответствующая ей часть обхода графа

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

Приложения к главе

84. Thoreau (1894), 419.

85. Quoted in Sachs, Stiebitz, and Wilson (1988).

86. Там же.

87. Quoted in Hopkins andWilson (2004).

88. Euler (1736), английский перевод в Biggs, Lloyd, and Wilson (1986), 3–8.

89. Ball (1892).

90. Hierholzer (1873).

91. Barabasi (2002), 12.

92. Listing (1847).

93. Terquem (1849).