Мосты Кёнигсберга и эйлеровы пути

Прогулка по семи мостам одного города не удалась горожанам, зато породила целую науку.

Эйлеров путь — маршрут в графе, проходящий по каждому ребру ровно один раз.

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

Перевод в граф

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

$$\text{эйлеров путь существует} \iff \text{число вершин нечётной степени равно } 0 \text{ или } 2.$$

В Кёнигсберге все четыре вершины имели нечётную степень — поэтому обход невозможен.

Проверяем критерий

from collections import Counter

# Граф Кёнигсберга: A,B — берега, C,D — острова
edges = [("A", "B"), ("A", "B"), ("A", "C"),
         ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]

deg = Counter()
for u, v in edges:
    deg[u] += 1
    deg[v] += 1

print("Степени вершин:", dict(deg))
odd = [v for v in deg if deg[v] % 2 == 1]
print("Вершины нечётной степени:", odd, "— их", len(odd))
print("Эйлеров путь существует:", len(odd) in (0, 2))
print("Сумма степеней:", sum(deg.values()), "= 2 * число рёбер =", 2 * len(edges))

Вывод:

Степени вершин: {'A': 5, 'B': 3, 'C': 3, 'D': 3}
Вершины нечётной степени: ['A', 'B', 'C', 'D'] — их 4
Эйлеров путь существует: False
Сумма степеней: 14 = 2 * число рёбер = 14

Как работает под капотом

Почему именно чётность? Каждый раз, проходя через вершину «насквозь», мы используем два ребра — одно чтобы войти, другое чтобы выйти. Значит, у всех промежуточных вершин степень должна быть чётной. Исключение — начало и конец маршрута: там одно ребро «непарное». Поэтому нечётных вершин может быть либо 0 (замкнутый цикл), либо ровно 2 (путь из одной в другую). В Кёнигсберге их четыре — на две «лишние» не хватает. Кстати, обратите внимание: сумма всех степеней равна удвоенному числу рёбер — каждое ребро добавляет по единице к двум вершинам. Отсюда следствие: вершин нечётной степени всегда чётное число.

Частые ошибки

Не путайте эйлеров путь (по всем рёбрам) с гамильтоновым (по всем вершинам) — это разные и совсем не похожие по сложности задачи. Условие на нечётные вершины — «0 или 2», а не «не более 2 любых»: трёх нечётных вершин не бывает в принципе. И помните: критерий работает для связного графа.

Итог

Граф = вершины (точки) + рёбра (связи).
Степень вершины — число подходящих рёбер.
Эйлеров путь существует, если нечётных вершин 0 или 2.
В Кёнигсберге все 4 вершины нечётные — обход невозможен.