Эйлеров обход

Пройти все рёбра по одному разу

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

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

Критерий существования

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

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

Три примера

1. Треугольник имеет степени 2, 2, 2. Обход $A-B-C-A$ проходит каждое ребро один раз и возвращается к началу.
2. Цепочка $A-B-C-D$ имеет нечётные вершины $A,D$. Эйлеров обход начинается на одном конце и заканчивается на другом.
3. Звезда с тремя листьями имеет степени 3, 1, 1, 1. Нечётных вершин четыре, поэтому пройти все рёбра ровно один раз нельзя.

Ошибки

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