Эйлеров цикл: пройти каждое ребро ровно один раз

Если ты знаешь условие существования эйлерова цикла и умеешь строить его стеком за O(V + E), листай до «Теперь сам».

Как думаешь, когда можно обойти все улицы ровно по разу

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

Прежде чем читать дальше, попробуй угадать признак по картинке: перекрёсток, где сходятся три улицы. Машина въехала по одной, выехала по другой. Что будет с третьей? Если ответил «на неё придётся заехать ещё раз и выехать по уже пройденной» - ты нашёл условие целиком.

На что это похоже

Рисунок «не отрывая карандаша от бумаги». Конверт с крестом внутри нарисовать одним росчерком нельзя, а «домик» без нижней стороны - можно, но только начав из определённого угла. Каждая точка, через которую карандаш проходит насквозь, получает два штриха: вход и выход. Значит, у точки, через которую только проходят, число штрихов чётно. Нечётным оно может быть только там, где росчерк начинается или кончается.

Механизм: условие и алгоритм Хирхольцера

УСЛОВИЕ (неориентированный граф, все вершины с рёбрами связаны)
    все степени чётны              → эйлеров цикл есть
    ровно две нечётные             → эйлеров путь между ними
    нечётных больше двух           → ни цикла, ни пути
ориентированный: вход = выход у всех → цикл
    (число нечётных вершин всегда чётно: сумма степеней = 2·E)

ХИРХОЛЬЦЕР
стек = [старт];  ответ = []
пока стек не пуст:
    v = вершина на вершине стека
    если у v есть неиспользованное ребро v–u:
        пометить ребро, положить u в стек
    иначе:
        снять v со стека и дописать в ответ
ответ, прочитанный задом наперёд, - эйлеров цикл

Почему это работает. При чётных степенях обход, вышедший из старта, может застрять только в самом старте: в любую другую вершину он вошёл, и раз ребро входа нечётное по счёту, выход ещё есть. Застряв, алгоритм отступает по стеку до вершины, у которой остались рёбра, и оттуда начинает новый замкнутый обход - он вклеится в ответ ровно на месте этой вершины. Каждое ребро кладётся в стек один раз и снимается один раз: O(V + E), если держать для каждой вершины указатель на следующее непросмотренное ребро.

Правило

Эйлеров цикл существует, когда все вершины с рёбрами связаны и все степени чётны (в ориентированном графе - вход равен выходу у каждой вершины); эйлеров путь - когда нечётных вершин ровно две, и начинать надо в одной из них. Алгоритм Хирхольцера идёт по неиспользованным рёбрам, складывая вершины в стек, а упёршись - снимает вершину в ответ; ответ задом наперёд - цикл. Время O(V + E).

Разбор: два треугольника с общей вершиной

рёбра: 1–2, 2–3, 3–1, 3–4, 4–5, 5–3
степени: 1:2  2:2  3:4  4:2  5:2 - все чётные, граф связен

стек 1                  берём 1–2
стек 1 2                берём 2–3
стек 1 2 3              берём 3–1
стек 1 2 3 1            у 1 рёбер нет  → ответ: 1
стек 1 2 3              у 3 есть 3–4   → берём
стек 1 2 3 4            берём 4–5
стек 1 2 3 4 5          берём 5–3
стек 1 2 3 4 5 3        рёбер нет      → ответ: 1 3
                        дальше рёбер нет ни у кого: снимаем всё
ответ: 1 3 5 4 3 2 1    задом наперёд: 1 2 3 4 5 3 1

Первый обход 1 → 2 → 3 → 1 вернулся в старт и застрял, пропустив петлю 3 → 4 → 5 → 3. Отступая, алгоритм нашёл в вершине 3 неиспользованное ребро и прошёл петлю - а в ответе она оказалась вставленной ровно между 2 → 3 и 3 → 1. Никакой отдельной «склейки» в коде нет: её делает стек.

Разбор: кодовый замок и последовательность де Брёйна

Кодовый замок принимает четырёхзначный двоичный код и проверяет ПОСЛЕДНИЕ четыре нажатия. Сколько нажатий нужно, чтобы перебрать все 16 кодов? Если вводить их по отдельности - 64. Но коды могут перекрываться: строка, в которой каждое из 2^k слов длины k встречается подряд ровно один раз, называется последовательностью де Брёйна, и строится она эйлеровым циклом.

вершины - слова длины k − 1; из вершины w два ребра:
    w → (w без первой цифры) + 0     и     w → (w без первой цифры) + 1
ребро = слово длины k; у каждой вершины 2 входа и 2 выхода → цикл есть
пройти все рёбра по разу = выписать все k-значные слова, перекрывая их

def ejlerov_cikl(sosedi, start):     # Хирхольцер, ориентированный граф
    sled = {v: 0 for v in sosedi}    # сколько рёбер вершины уже взято
    stek, cikl, shagi = [start], [], 0
    while stek:
        v = stek[-1]
        if sled[v] < len(sosedi[v]):  # есть неиспользованное ребро
            u = sosedi[v][sled[v]]
            sled[v] += 1
            stek.append(u)
            shagi += 1
        else:                         # тупик - вершина в ответ
            cikl.append(stek.pop())
    return cikl[::-1], shagi


def de_brejn(k):                      # каждое k-значное двоичное слово
    m = 2 ** (k - 1)                  # вершины - слова длины k − 1
    sosedi = {v: [(2 * v + b) % m for b in (0, 1)] for v in range(m)}
    cikl, shagi = ejlerov_cikl(sosedi, 0)
    # ребро v → u дописывает последнюю цифру u
    stroka = "0" * (k - 1) + "".join(str(u % 2) for u in cikl[1:])
    return stroka, shagi


s, shagi = de_brejn(4)
print("k=4:", s, "длина", len(s))
for k in (4, 10, 16):
    s, shagi = de_brejn(k)
    vse = {s[i:i + k] for i in range(len(s) - k + 1)}
    print(f"k={k}: рёбер {shagi}, разных слов {len(vse)}"
          f" из {2 ** k}, длина {len(s)}")

k=4: 0000100110101111000 длина 19
k=4: рёбер 16, разных слов 16 из 16, длина 19
k=10: рёбер 1024, разных слов 1024 из 1024, длина 1033
k=16: рёбер 65536, разных слов 65536 из 65536, длина 65551

19 нажатий вместо 64 - и это минимум: строка длины L содержит L − k + 1 слов подряд, а слов нужно 16. Для шестнадцатизначного кода - 65551 нажатие вместо миллиона с лишним. Число пройденных рёбер ровно равно числу рёбер графа: каждое ребро взято один раз, работа линейна.

Что ломается без этого

Первая ошибка - проверить чётность степеней и забыть связность: два отдельных треугольника имеют все степени по два, а единого цикла нет. Вторая - для пути начинать не с нечётной вершины: обход застрянет во второй нечётной, оставив рёбра непройденными. Третья - строить цикл «жадно» (идти, пока идётся, и считать результат ответом): первый замкнутый обход может пропустить петли, как 3 → 4 → 5 → 3 в разборе, и без стека их не вклеить. Четвёртая - на каждом шаге искать неиспользованное ребро с начала списка соседей: на вершине высокой степени это квадрат; нужен указатель «следующее непросмотренное ребро» для каждой вершины.

Зачем это в работе

Маршруты по рёбрам: снегоуборка, полив улиц, сбор мусора, обход линий электропередачи, проверка всех переходов в схеме состояний программы - везде, где «посетить» нужно связь, а не точку. Если у графа есть нечётные вершины, это задача китайского почтальона: какие улицы пройти дважды, чтобы лишний путь был минимальным. Когда нечётных вершин две - дублируют кратчайший путь между ними (о кратчайших путях - следующий раздел); в общем случае нечётные вершины разбивают на пары паросочетанием минимальной стоимости. Последовательности де Брёйна сидят в сборке генома из коротких прочтений (там граф строят из перекрывающихся кусков ДНК), в генераторах тестов и в позиционных кодах для роботов.

Теперь сам

Граф: рёбра A–B, B–C, C–A, C–D, D–B. Есть ли эйлеров цикл? Эйлеров путь? Если путь есть - откуда начинать и какой он?