— Генри Дэвид Торо84

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

Рис. 11.1. Графы

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

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

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

Может ли пешеход обойти все семь мостов, не проходя ни по какому дважды?

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

Следовательно, Ты можешь убедиться, славнейший муж, что это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне не понятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике85.

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

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

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

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

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

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

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

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

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

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

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