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

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

В этом письме Эйлер употребил предложенный Лейбницем термин 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. Граф называется связным, если из любой вершины можно дойти до любой другой, следуя по ребрам.

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

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

Существует ли для графа кёнигсбергских мостов (рис. 11.3) эйлеров обход? Вообще, как узнать, существует для произвольного графа эйлеров обход?

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