Обход графа (эйлеров путь)

Определение. Эйлеров путь

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

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

Критерий эйлерова пути

Существование эйлерова пути определяется степенями вершин:

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

Ориентированный граф

Ориентированный граф (орграф) — граф, в котором каждое ребро имеет направление и изображается стрелкой. Такие рёбра называются дугами. Обычный граф без направлений называется неориентированным.

Пример 1. Проверка существования эйлерова цикла

Дан граф с рёбрами A–B, B–C, C–D, D–A. Существует ли эйлеров цикл?

Дано: рёбра: A–B, B–C, C–D, D–A.

Формула: эйлеров цикл существует, если граф связный и все степени чётные.

Подстановка: степени: $\deg(A)=2$, $\deg(B)=2$, $\deg(C)=2$, $\deg(D)=2$. Все чётные, граф связный.

Ответ: эйлеров цикл существует, например A–B–C–D–A.

Пример 2. Проверка существования эйлерова пути

Дан граф с рёбрами A–B, B–C, C–D. Существует ли эйлеров путь?

Дано: рёбра: A–B, B–C, C–D.

Формула: эйлеров путь существует, если граф связный и имеет не более двух вершин нечётной степени.

Подстановка: степени: $\deg(A)=1$, $\deg(B)=2$, $\deg(C)=2$, $\deg(D)=1$. Нечётные вершины: A и D — ровно две.

Ответ: эйлеров путь существует: A–B–C–D. Он начинается в A и заканчивается в D.

Пример 3. Задача о Кёнигсбергских мостах

В графе Кёнигсберга четыре вершины (части города) со степенями 3, 3, 3, 5. Можно ли пройти по каждому мосту ровно один раз?

Дано: степени вершин: 3, 3, 3, 5.

Формула: эйлеров путь существует, если нечётных вершин не более двух.

Подстановка: все четыре степени нечётные — нечётных вершин четыре, что больше двух.

Ответ: эйлерова пути не существует — пройти по каждому мосту ровно один раз невозможно.

Важно!

⚠️ Типичная ошибка — забывать проверять связность графа. Даже если все степени чётные, но граф распадается на две отдельные части, эйлерова пути нет: нельзя перейти из одной части в другую. Сначала убедись, что граф связный, и только потом смотри на степени.