Эйлеров путь и цикл: условия существования и алгоритм поиска

Коротко

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

Задача, с которой всё началось

В Кёнигсберге было семь мостов через реку. Горожане спорили: можно ли пройти по всем мостам ровно по одному разу и вернуться домой?

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

Представим участки суши вершинами, мосты — рёбрами. Каждый раз, когда мы входим в вершину, мы должны из неё выйти — то есть используем два ребра. Значит для замкнутого маршрута у каждой вершины должно быть чётное число рёбер.

В Кёнигсберге все четыре вершины имели нечётную степень. Ответ: маршрута не существует.

Условия существования

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

Эйлеров цикл существует, если:

• граф связен (по рёбрам — изолированные вершины без рёбер не мешают);
• все вершины имеют чётную степень.

Эйлеров путь (не цикл) существует, если:

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

Заметьте: нечётных вершин не может быть ровно одна. Сумма всех степеней равна удвоенному числу рёбер, то есть чётна, поэтому нечётных вершин всегда чётное количество.

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

Эйлеров цикл: для каждой вершины входящая степень == исходящая степень.

Эйлеров путь: у одной вершины исход − вход = 1 (старт), у другой вход − исход = 1 (финиш), у остальных равенство.

Проверка на Python

def has_eulerian(graph: dict) -> str:
    odd = [v for v in graph if len(graph[v]) % 2 == 1]

    # проверяем связность вершин, у которых есть рёбра
    non_empty = [v for v in graph if graph[v]]
    if non_empty:
        visited = set()
        stack = [non_empty[0]]
        while stack:
            v = stack.pop()
            if v in visited:
                continue
            visited.add(v)
            stack.extend(graph[v])

        if not set(non_empty) <= visited:
            return 'нет (граф несвязен)'

    if len(odd) == 0:
        return 'эйлеров цикл'
    if len(odd) == 2:
        return f'эйлеров путь, от {odd[0]} до {odd[1]}'
    return f'нет ({len(odd)} вершин нечётной степени)'


square = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}
print(has_eulerian(square))   # эйлеров цикл

path_graph = {1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]}
print(has_eulerian(path_graph))  # эйлеров путь, от 1 до 2

Алгоритм Хирхольцера

Само построение маршрута делается алгоритмом Хирхольцера за O(E). Идея:

1. Идём из стартовой вершины куда глаза глядят, вычёркивая пройденные рёбра, пока не упрёмся в тупик.
2. Полученный маршрут может не покрыть все рёбра. Тогда находим на нём вершину, из которой ещё выходят неиспользованные рёбра, и строим из неё второй цикл.
3. Вставляем второй цикл в первый на месте этой вершины.
4. Повторяем, пока рёбра не кончатся.

На практике это красиво реализуется через стек.

from collections import defaultdict


def hierholzer(graph: dict, start=None) -> list:
    # копируем списки смежности — будем их разрушать
    adj = {v: list(neighbors) for v, neighbors in graph.items()}

    odd = [v for v in adj if len(adj[v]) % 2 == 1]
    if len(odd) not in (0, 2):
        return []          # эйлерова маршрута нет

    if start is None:
        start = odd[0] if odd else next(v for v in adj if adj[v])

    stack = [start]
    path = []

    while stack:
        v = stack[-1]

        if adj[v]:
            u = adj[v].pop()          # берём любое неиспользованное ребро
            adj[u].remove(v)          # удаляем обратное направление
            stack.append(u)
        else:
            # из вершины больше не выйти — она уходит в маршрут
            path.append(stack.pop())

    return path[::-1]


square = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}
print(hierholzer(square))
# [1, 4, 3, 2, 1] — обошли все четыре ребра и вернулись

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

Строка adj[u].remove(v) работает за O(степень) и портит общую сложность. В боевом коде рёбра помечают как использованные по индексу — тогда получается честные O(E).

Эйлеров путь и гамильтонов путь

Их постоянно путают, а разница принципиальная.

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

Практические применения

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

Сборка генома. В биоинформатике фрагменты ДНК склеивают, строя граф де Брёйна и находя в нём эйлеров путь. Это реальное промышленное применение.

Рисование фигуры одним росчерком. Классическая головоломка — прямое применение критерия. Конверт с диагоналями нарисовать можно (две нечётные вершины), а конверт с обеими диагоналями крест-накрест — уже нет.

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

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

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

Неправильный старт. Если есть две нечётные вершины, начинать надо обязательно с одной из них. Старт из чётной вершины приведёт в тупик до того, как обойдутся все рёбра.

Забытое удаление обратного ребра. В неориентированном графе ребро хранится в двух списках, и убрать надо оба.

Ответ без разворота. Алгоритм собирает маршрут с конца, поэтому финальный [::-1] обязателен. Для цикла разницы не видно, а для пути направление получится обратным.

Что запомнить

• Эйлеров маршрут проходит по каждому ребру ровно один раз.
• Цикл существует при всех чётных степенях, путь — ровно при двух нечётных.
• Нечётных вершин всегда чётное количество — одной быть не может.
• Алгоритм Хирхольцера строит маршрут за O(E) через стек.
• Не путайте с гамильтоновым путём: тот про вершины и NP-полон.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→