Семь мостов Кёнигсберга

Анализ Эйлера

Во-первых, Эйлер указал, что выбор маршрута внутри каждого массива суши не имеет значения. Единственным важным свойством маршрута является порядок пересечения мостов. Таким образом, он перевел проблему в абстрактные термины. Это заложило основы теории графов. Он убрал все характеристики, кроме списка массивов суши и мостов, соединяющих их. На языке теории графов он заменил каждый массив суши абстрактной "вершиной" или узлом. Затем он заменил каждый мост абстрактным соединением, "ребром". Ребро (дорога) фиксировало, какие две вершины (массивы суши) были соединены. Таким образом, он сформировал граф.

→ →

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

Далее Эйлер заметил, что (за исключением конечных точек прогулки), всякий раз, когда человек входит в вершину по мосту, он выходит из нее по мосту. В любой прогулке по графу количество входов в вершину равно количеству выходов из нее. Если каждый мост был пересечен ровно один раз, то из этого следует, что для каждого участка суши (кроме тех, которые выбраны для старта и финиша) количество мостов, касающихся этого участка, должно быть четным. Это объясняется тем, что если существует n мостов, то его пересекают ровно 2n раз. Однако все четыре массива суши в исходной задаче имеют нечетное количество мостов (один из них имеет 5 мостов, а каждый из трех других - по 3). Существует не более двух массивов, которые могут быть конечными точками прогулки. Таким образом, предложение о том, что пешеход пересекает каждый мост один раз, приводит к противоречию.

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

Работа Эйлера была представлена Санкт-Петербургской академии 26 августа 1735 года. Она была опубликована под названием Solutio problematis ad geometriam situs pertinentis (Решение задачи, относящейся к геометрии положения) в журнале Commentarii academiae scientiarum Petropolitanae в 1741 году. На английском языке она доступна в журнале The World of Mathematics.

Значение в истории математики

В истории математики решение Эйлером проблемы кенигсбергского моста считается первой теоремой теории графов. Теория графов - это предмет, который сейчас принято рассматривать как ветвь комбинаторики.

Современное состояние мостов

Два из семи первоначальных мостов были разрушены во время бомбардировки Кенигсберга во время Второй мировой войны. Два других были позже снесены. На их месте была проложена современная автомагистраль. Три других моста сохранились, хотя только два из них относятся ко времени Эйлера (один был перестроен в 1935 году). Таким образом, по состоянию на 2000 год в Калининграде было пять мостов.

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

Похожие страницы

• Икосианская игра
• Гамильтонов путь
• Вода, газ и электричество
• Проблема путешествующего коммивояжера