Информатика · объяснение и практика

Как стек Хиерхольцера собирает маршрут из использованных рёбер

Построить эйлеров маршрут стеком Хиерхольцера и независимо проверить точное совпадение мультимножества пройденных и исходных рёбер.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

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

Метод и постановка

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

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

Проверка и границы вывода

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

Для независимой проверки составьте мультимножество соседних пар в готовой последовательности. После приведения концов каждой пары к одному неориентированному порядку оно должно совпасть с исходным набором рёбер. Одной проверки числа шагов недостаточно: она может пропустить повтор одного ребра вместо другого. При m рёбрах список содержит m+1 записей вершин. Повтор одинакового номера в разных местах допустим. Пустой по рёбрам граф получает тривиальный маршрут из одной вершины; это не утверждение о существовании нетривиального цикла или гамильтонова пути.

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

Пример

Соединим квадрат 1–2–3–4–1 с треугольником 2–5–6–2. У общей вершины 2 степень четыре, у остальных два. Подходящий маршрут: 1→2→5→6→2→3→4→1.

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

От чтения к действию

А теперь — вы

Все степени чётные, но рёбра находятся в двух непустых несвязных компонентах. Есть ли один эйлеров обход всех рёбер?

Частые вопросы

Изолированная вершина мешает маршруту по рёбрам?

Нет, если все непустые рёбра лежат в одной компоненте.

Это путь без повторения вершин?

Нет. Повторяться могут вершины; каждое ребро используется ровно один раз.

Углублённый разбор

Баланс ориентированного эйлерова маршрута

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

Перед началом: Входящая и исходящая степень; Эйлеров обход.

Начало и конец объясняют дисбаланс

При прохождении внутренней вершины каждому использованному входу соответствует последующий выход. Поэтому для замкнутого маршрута out(v)=in(v) во всех вершинах. Для открытого маршрута из s в t нужны out(s)−in(s)=1,in(t)−out(t)=1, а у остальных баланс 0. Если положительных или отрицательных исключений больше одного, один маршрут невозможен.

Это условия для ориентированного графа или мультиграфа с отдельными идентификаторами дуг. Кратные дуги считаются разными объектами и должны использоваться каждая один раз. Отбрасывание направления до подсчёта степеней теряет требуемый баланс, даже если неориентированная картина допускает хороший обход.

Слабая связность вместе с балансом достаточна

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

В таком графе строится ориентированный эйлеров цикл. Разрезав его после искусственной дуги и удалив её, получаем маршрут из s в t. Это доказывает достаточность, а не только даёт способ угадать начало. Для замкнутого случая искусственная дуга вообще не нужна, поскольку баланс уже нулевой.

Проверка готового маршрута использует направленные пары

Перечень соседних вершин маршрута должен совпасть с исходным мультимножеством направленных дуг. Нельзя нормализовать пары сортировкой концов, как в неориентированном случае: пары a→b и b→a различны. Одна правильная длина m+1 не обнаружит замену одной дуги другой.

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

Шесть направленных шагов

Условие. Даны дуги s→a,a→b,b→a,a→t,t→s,s→t. Найдите начало, конец и маршрут, использующий каждую дугу один раз.

  1. У s две исходящие и одна входящая дуга, поэтому его баланс+1. У t одна исходящая и две входящие, баланс−1.
  2. У a входов и выходов по два, у b по одному. Поддержка слабо связна, значит условия существования выполнены.
  3. Маршрут s→a→b→a→t→s→t имеет шесть шагов и начинается/заканчивается в требуемых исключительных вершинах.
  4. Его направленные соседние пары по одному разу дают все шесть исходных дуг. Повтор вершины a или s допустим: ограничение относится к дугам.

Ответ. Начало s, конец t; подходит s,a,b,a,t,s,t.

Проверка. Независимый перебор порядков шести дуг находит маршрут с теми же концами. Попытка начать в a не может исправить баланс+1 у s и потому не даёт полного направленного обхода.

Где легко ошибиться. Чётность неориентированных степеней не заменяет направленный баланс. Для контроля маршрута сохраняйте порядок концов каждой дуги и её идентификатор.

Проверьте понимание

Где должен начинаться открытый маршрут задачи?

Вопросы к этой главе

Сильная связность обязательна для открытого маршрута?

Нет. Вершина конца может не иметь пути обратно к началу. Баланс и слабая связность поддержки являются правильными условиями для открытого случая.

Зачем искусственная дуга?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NetworkX: has_eulerian_path

    Официальная документация: сверены направленные балансы и слабая связность. Глава явно удаляет изолированные вершины из поддержки рёбер, отличая этот договор от строгого поведения функции NetworkX.

Кратчайшее повторение рёбер в задаче почтальона

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

Перед началом: Чётность степеней; Кратчайший путь.

Повторения должны исправить все нечётные вершины

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

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

Метрика кратчайших путей даёт нижнюю границу и конструкцию

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

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

Жадная пара может испортить оставшееся спаривание

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

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

Дешёвая пара оставляет дорогой хвост

Условие. В K4 веса AB=1,AC=AD=BC=BD=2,CD=100. Найдите минимальную длину замкнутого обхода всех рёбер.

  1. Все четыре степени равны 3, поэтому T={A,B,C,D}. Обязательная сумма исходных весов равна 109.
  2. Расстояние C,D равно 4 через A или B, остальные парные расстояния совпадают с дешёвыми прямыми рёбрами. Спаривания AB+CD,AC+BD,AD+BC стоят 5,4,4.
  3. Минимальная добавка 4 достигается повторением AC и BD. Общая длина 109+4=113.
  4. Один обход расширенной сети:A→B→D→B→C→A→D→C→A. Повторяются только AC и BD, а дорогое CD пройдено ровно один раз.

Ответ. Минимальная длина 113; жадное первое спаривание AB дало бы добавку 5 и итог 114.

Проверка. Прямое сложение восьми весов предъявленного маршрута даёт 113. Все три паросочетания перечислены, поэтому добавку меньше 4 исключает независимая конечная проверка.

Где легко ошибиться. Метрика кратчайших путей оценивает повторения, не отменяя обязательного прохода исходного дорогого ребра. Сначала сохраните всю исходную сумму, затем оптимизируйте добавку.

Проверьте понимание

Какова минимальная полная длина обхода в задаче?

Вопросы к этой главе

Что если нечётных вершин нет?

Добавочная длина 0, и минимальный маршрут является эйлеровым циклом с суммой всех исходных весов. Неотрицательность весов исключает выгоду от лишних повторений.

Можно тем же способом решить ориентированную задачу?

Нет. Там исправляется дисбаланс входов/выходов, а не нечётность. Возникает другая транспортная или потоковая постановка с направленными расстояниями.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Larson, Odoni: Urban Operations Research, §6.4.4

    Первичный авторский учебник MIT: прочитаны шаги 1–4, минимальное паросочетание по кратчайшим расстояниям и добавление копий путей. Собственный K4 с дорогим ребром и ловушкой жадного выбора не повторяет рисунок 6.15; оригинальный PDF Edmonds—Johnson не прочитан из-за таймаута.

Теорема BEST считает ориентированные эйлеровы обходы

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

Перед началом: Баланс степеней ориентированного эйлерова графа; Арборесценция, направленная к корню.

Фиксированная первая дуга устраняет неоднозначность вращения

Пусть ориентированный мультиграф сильно связен на вершинах с дугами и для каждой вершины входящая степень равна исходящей d_v. Все дуги имеют разные идентификаторы, даже если их концы совпадают. Зафиксируем первую дугу e с началом w и считаем полные последовательности дуг, начинающиеся именно с неё.

Тогда число обходов равно t_w·∏_v(d_v−1)!, где t_w — число остовных арборесценций к w: у каждой другой вершины одно исходящее ребро дерева, у w ни одного. Если фиксировать только начальную вершину и разрешить любую первую дугу, результат нужно умножить на d_w. Это разные пространства подсчёта, и их нельзя смешивать в одном ответе.

Последние выходы образуют дерево, а остальные можно переставлять

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

После выбора дерева у v≠w последняя дуга уже фиксирована, а остальные d_v−1 исходящих дуг можно упорядочить (d_v−1)! способами. В корне фиксирована первая e, и оставшиеся d_w−1 дуг тоже имеют такой факториал порядков. Следование этим локальным спискам использует все дуги; дерево последних выходов препятствует преждевременному завершению с неиспользованной частью.

Петля и параллельность по-разному влияют на множители

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

При удалении меток параллельных дуг получится другая комбинаторная задача. Нельзя без доказательства использовать прежнюю формулу или произвольно делить её на факториалы. В малом примере полезно независимо перебрать последовательности помеченных дуг и проверить направление каждого перехода, полноту использования и фиксированное начало.

Три параллельные пары и одна петля

Условие. Между a и b идут дуги e₁,e₂,e₃ из a в b и f₁,f₂,f₃ из b в a. В a имеется петля l. Сколько эйлеровых обходов начинается с фиксированной e₁?

  1. Исходящие степени равны d_a=4 и d_b=3, входящие совпадают с ними. Граф сильно связен, поэтому условия ориентированной формулы выполнены.
  2. Арборесценция к a выбирает одну из трёх дуг f_i из b в a. Петля l в дерево не входит, поэтому t_a=3.
  3. Формула даёт 3·(4−1)!·(3−1)!=3·6·2=36 обходов с первой дугой e₁.
  4. Независимый подсчёт: после фиксированной e₁ оставшиеся e₂,e₃ можно упорядочить двумя способами, три f — шестью. Петлю можно поставить в один из трёх последующих приходов в a, получая 2·6·3=36.
  5. Если первая дуга не фиксирована, а задан только старт a, ответ равен 4·36=144. Если ошибочно забыть петлю, получится 12, что относится к другому графу.

Ответ. При фиксированной первой помеченной дуге e₁ число обходов равно 36. При одном лишь фиксированном старте a — 144.

Проверка. Полный перебор перестановок шести оставшихся помеченных дуг после e₁ оставляет ровно 36 корректных замкнутых маршрутов. Он независимо проверяет оба факториала и учёт петли.

Где легко ошибиться. Не подставляйте число обходов с произвольной первой дугой в формулу для закреплённой e₁. Разница равна числу исходящих дуг старта и в примере даёт множитель четыре.

Проверьте понимание

Сколько помеченных эйлеровых обходов начинается именно с e₁?

Вопросы к этой главе

Почему дерево выбирает последнюю дугу только у b?

Корень a является местом окончательного завершения. Для остальных вершин последний выход обязан вести по дереву к корню; корню исходящая дуга дерева не нужна.

Почему петля увеличивает число обходов, но не число деревьев?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Farrell, Levine: Multi-Eulerian tours of directed graphs

    Прочитана теорема 1 с фиксированной первой дугой и формулой BEST для ориентированного мультиграфа, включая определение арборесценций. Обобщение на π-обходы не используется. Пример с тремя параллельными парами и петлёй проверен полным перебором помеченных последовательностей.

Цикл де Брёйна содержит каждый блок ровно один раз

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

Перед началом: Ориентированный эйлеров цикл и баланс входов/выходов; Префикс, суффикс и циклические окна.

Каждое окно представляется отдельной дугой

Алфавит из k≥2 символов и порядок n≥2; циклическое слово содержит каждое слово длины n ровно в одном циклическом окне.

Строим k^(n−1) вершин — все слова длины n−1. Слово c₁…cₙ задаёт дугу из c₁…cₙ₋₁ в c₂…cₙ, помеченную последней буквой cₙ. Из каждой вершины выходят k дуг и входят k дуг. Петли допустимы: постоянное слово задаёт необходимое окно из одинаковых символов.

Граф сильно связен: чтобы из любого состояния попасть в заданное, достаточно последовательно дописать буквы целевого состояния. Баланс и связность обеспечивают эйлеров цикл. Здесь используется ориентированный баланс степеней; правило чётности неориентированного графа не заменяет эту проверку.

Чтение меток должно учитывать кольцевую границу

Если начать с вершины длины n−1 и дописывать метку каждой пройденной дуги, получится линейная строка длины k^n+n−1. Её первые k^n символов образуют кольцевую последовательность, а последние n−1 повторяют начальный фрагмент, замыкая окна. Эквивалентно можно читать только метки дуг по кругу; это даст циклический сдвиг той же записи.

Всего требуется k^n разных окон, а кольцо длины L имеет ровно L начал окон. Поэтому длина не меньше k^n; эйлерова конструкция достигает нижней границы. Линейная запись со явно дописанным хвостом длиннее кольца, но не является контрпримером минимальности. Важно заранее договориться, какой из двух форматов возвращается.

Полный набор состояний отличается от линейного регистра

Регистр с примитивным многочленом проходит ненулевые состояния и оставляет нулевое неподвижным. Максимальный период такого регистра сам по себе не даёт кольцо со всеми k^n окнами: постоянное нулевое окно тоже должно присутствовать. Здесь полнота получается из точного использования всех дуг графа, а не из порядка элемента конечного поля.

Графовая реализация требует память для экспоненциально большого относительно n набора дуг. Линейность эйлерова обхода относится к числу k^n дуг, а не к самому параметру n. Существуют более компактные специальные конструкции, но их свойства нельзя приписывать простому хранению всего графа. Конечная проверка должна считать все циклические окна с кратностями, а не только различные буквы.

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

Условие. Постройте последовательность де Брёйна порядка 2 над алфавитом {0,1,2}. Вершины графа — 0,1,2; требуется использовать все девять ориентированных дуг, включая петли.

  1. У каждой вершины есть дуги в 0,1,2, по три входа и выхода. Стековый эйлеров алгоритм с приоритетом меньшего ещё не использованного соседа даёт обход 0,0,1,0,2,1,1,2,2,0.
  2. Смежные пары этого обхода равны 00,01,10,02,21,11,12,22,20. Это все девять упорядоченных пар без повторов.
  3. Линейная запись вершин равна 0010211220. Последний нуль замыкает начальное односимвольное состояние. Убираем только этот повторённый хвост и получаем кольцо 001021122 длины 9.
  4. Последнее циклическое окно начинается с последней двойки и заканчивается первым нулём, давая 20. Если проверять только пары внутри девятисимвольной линейной записи, одно требуемое окно будет потеряно.

Ответ. Подходит циклическая последовательность 001021122 длины 9; её линейная развёртка с замыкающим хвостом — 0010211220.

Проверка. Независимый перебор девяти циклических начал даёт мультимножество всех пар {0,1,2}², каждая с частотой 1. Нижняя граница по числу начал равна 3²=9, поэтому более короткое кольцо невозможно.

Где легко ошибиться. Не удаляйте петли из графа перекрытий как будто они бесполезны. Они кодируют окна 00,11,22, которые требуются наравне с остальными.

Проверьте понимание

Какова минимальная длина кольца со всеми парами над {0,1,2} в разобранной задаче?

Вопросы к этой главе

Смена начальной вершины даёт неправильный ответ?

Нет, если получен корректный эйлеров цикл. Она может изменить циклический сдвиг или саму допустимую последовательность; проверка должна удостоверять набор окон, а не единственный заранее заданный текст.

Почему пример содержит десять записей вершин, но ответ имеет длину девять?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Sawada, Williams — De Bruijn Sequences, graph model

    Граф перекрытий и соответствие эйлерова цикла всем окнам. В источнике порядок графа задаётся длиной вершин; здесь явно использованы вершины длины n−1. Трёхбуквенный обход и его окна проверены независимо.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться