1) Формальная проверка существования эйлерова обхода в неориентированном графе
- Обозначения: $G=(V,E)$, степень вершины $v$ — $\mathrm{deg}(v)$. Пусть $V_0=\{v\in V:\mathrm{deg}(v)>0\}$.
- Необходимое и достаточное условие для эйлерова цикла: подграф, индуцированный на $V_0$, связен и для всех $v\in V$ выполнено $\mathrm{deg}(v)$ чётно.
- Для эйлерова тропа (маршрут, который может начинаться и заканчиваться в разных вершинах): подграф на $V_0$ связен и ровно $0$ или $2$ вершины имеют нечетную степень. Если нечётных $=2$, то начало — одна из них, конец — другая.
Проверки по шагам:
- Посчитать степени всех вершин: за время \(\(O(|V|+|E|)\)\).
- Найти произвольную вершину $s\in V_0$ и выполнить DFS/BFS по неориентированному графу, считая только вершины из $V_0$; убедиться, что все вершины $V_0$ достижимы: \(\(O(|V|+|E|)\)\).
- Подсчитать количество вершин с нечётной степенью: если 0 → цикл, если 2 → тропа, иначе эйлерова обхода нет.
2) Алгоритм построения эйлерова цикла/тропа (Иерхолцера — Hierholzer)
Идея: пройти по ребрам, пока есть неиспользованные, образуя цикл; если цикл не покрывает все ребра, вставить в него дополнительные циклы в вершинах с неиспользованными ребрами.
Псевдокод (реализация на списках смежности, итеративно со стеком):
- Вход: $G=(V,E)$, стартовая вершина $s$ (если троп — выберите одну из нечётных, иначе любую из $V_0$).
- Используйте структуру для неиспользованных рёбер (итераторы по спискам смежности).
- Стек $stack\leftarrow [s]$, список результата $path\leftarrow []$.
- Пока $stack$ не пуст:
- $v\leftarrow$ верх стека.
- Если у $v$ есть непомеченное ребро $v-u$:
- пометьте ребро использованным и запушьте $u$ в $stack$.
- Иначе: попните $v$ из $stack$ и добавьте его в начало/конец $path$.
- В результате $path$ содержит последовательность вершин эйлерова маршрута.
Сложность:
- Каждое ребро обрабатывается ровно один раз → время \(\(O(|E|)\)\) при использовании списков смежности и амортизационно-constant операциях; общая сложность с проверками \(\(O(|V|+|E|)\)\).
- Память: \(\(O(|V|+|E|)\)\).
Замечания: для мультиграфов алгоритм аналогичен; важно корректно помечать использованные копии рёбер.
3) Критерии для ориентированных графов
Обозначения: для вершины $v$ $\text{outdeg}(v)$, $\text{indeg}(v)$. Пусть $V_0$ — вершины, участвующие в рёбрах.
- Для эйлерова цикла в ориентированном графе: для всех $v$ выполнено $\text{indeg}(v)=\text{outdeg}(v)$ и каждая вершина из $V_0$ принадлежит одной сильной компоненте связности (или эквивалентно: граф, стронг-свёрнутый по ребрам с ненулевой степенью, сильно связен). Проверка сильной связности — алгоритмы Kosaraju/Tarjan за \(\(O(|V|+|E|)\)\).
- Для эйлерова пути (тропа) в ориентированном графе: либо выполняется условие цикла выше, либо существует ровно одна вершина $s$ с $\text{outdeg}(s)=\text{indeg}(s)+1$, ровно одна вершина $t$ с $\text{indeg}(t)=\text{outdeg}(t)+1$, и для всех остальных $\text{indeg}=\text{outdeg}$; кроме того все вершины из $V_0$ должны находиться в одной слабой компоненте связности, и (альтернативная формулировка) после добавления направленного ребра $t\to s$ граф становится сильносвязным. Проверки счётных величин за \(\(O(|V|)\)\) и связности за \(\(O(|V|+|E|)\)\).
Построение маршрута в ориентированном графе делается модификацией алгоритма Иерхолцера с учётом ориентированных рёбер; сложность та же \(\(O(|E|)\)\).
4) Практические применения (кратко, по запрошенным направлениям)
- Маршрутизация (доставка, почта, дорожные инспекции): модель улиц как рёбер графа; если нужно обойти каждую улицу хотя бы один раз, ищут эйлеров маршрут; если граф не эйлеров — решается задача китайского почтальона (Chinese Postman): дополнить/дублировать рёбра минимальным весом. Для неориентированного варианта: найти все нечётные вершины, вычислить кратчайшие пути между ними и решить задачу минимального паросочетания — сложность зависит от алгоритма паросочетания (в худшем случае ~\(\(O(n^3)\)\) для $n$ нечётных вершин). Для ориентированного варианта используют min-cost flow.
- Сбор мусора, чистка улиц, уборка снега: то же практическое требование — пройти по всем улицам; часто нужно минимизировать повторные проходы → Chinese Postman.
- Планирование маршрутов и логистика (включая сбор и развоз): при необходимости покрыть все связи/ребра (осмотр точек, патрулирование) либо при анализе потока — используют эйлеровы алгоритмы и их обобщения; в биоинформатике (сборка геномов) используются де Брейновы графы и эйлеровы пути для восстановления последовательностей.
Короткие рекомендации по применению:
- Если граф уже удовлетворяет эйлеровости — используйте Hierholzer для быстрого построения маршрута (\(\(O(|E|)\)\)).
- Если нет — решить задачу китайского почтальона: вычислить минимальную дополнение рёбер (неориентированный — через минимальное паросочетание нечётных вершин; ориентированный — через min-cost flow).
Если нужно, могу привести код-псевдо или пример реализации Hierholzer на конкретном языке.