Условие (коротко)
- Эйлеров цикл (замкнутый маршрут, проходящий по каждому ребру ровно один раз) существует в неориентированном графе $G=(V,E)$ тогда и только тогда, когда граф связен при опускании изолированных вершин и для каждой вершины $\mathrm{deg}(v)$ чётно: $\forall v\mathrm{deg}(v)\equiv 0(\mathrm{mod}2)$.
- Эйлеров путь (маршрут, не обязательно замкнутый, проходящий по каждому ребру ровно один раз) существует тогда и только тогда, когда граф связен при опускании изолированных вершин и ровно $0$ или $2$ вершины имеют нечётную степень (то есть число вершин с нечётной степенью равно $0$ или $2$).
Доказательство (кратко)
1. Необходимость.
- Каждый раз, посещая вершину по некоторому ребру, кроме возможного начала и конца пути, мы должны «выйти» по другому ребру. Поэтому входящие и выходящие переходы для внутренней вершины паруются, и $\mathrm{deg}(v)$ чётно. Для замкнутого маршрута нет особоёных нач/концов → все вершины чётны. Для открытого пути возможны ровно две вершины (начало и конец) с нечётной степенью.
- Если ребра покрыты одним маршрутом, то все вершины, по которым проходят ребра, лежат в одной компоненте связности → связность на непустых вершинах.
2. Достаточность.
- Для случая всех степеней чётны: взять любую вершину и построить произвольный цикл, всегда можно продолжать, пока есть неизрасходованные ребра. Удаление построенного цикла оставляет граф, в котором все степени опять чётны; каждую оставшуюся компоненту можно «вклеить» в уже построенный цикл в вершинах их пересечения. Итеративно получаем эйлеров цикл (классический аргумент Герихользера / Hierholzer).
- Для случая ровно двух нечётных вершин $u$ и $w$: добавить виртуальное ребро $(u,w)$, получим граф с всеми чётными степенями — он имеет эйлеров цикл; затем удалить виртуальное ребро, цикл распадается в эйлеров путь между $u$ и $w$.
Алгоритм построения (Hierholzer, эффективная реализация)
- Идея: идти по непосещённым ребрам, складывать вершины в стек; когда из вершины больше нет непосещённых рёбер — вынимать её в ответ; при появлении вершины в текущем цикле с ещё непосещёнными рёбрами — продолжать от неё и потом «вклеить» новый цикл.
- Реализация (итеративно, на adjacency-list с метками рёбер):
1. Выбрать стартовую вершину: если есть ровно две нечётные — старт = одна из них; иначе любую вершину с ненулевой степенью.
2. Поддерживать стек S и список результата R (порядок вершин цикла/пути). Помечать рёбра как использованные (по ID).
3. Пока стек не пуст:
- $v=$ верх стека; если у $v$ есть неиспользованное ребро $(v,u)$, пометить ребро использованным, положить $u$ в стек;
- иначе вынуть $v$ из стека и дописать в конец $R$.
4. $R$ даёт порядок вершин эйлерова пути/цикла; если число использованных рёбер меньше $|E|$, то граф был несвязан → эйлерова тропа/цикл отсутствует.
- Сложность: время $O(|E|)$ при представлении списками смежности и пометке рёбер, память $O(|V|+|E|)$.
- Примечания: для мультiграфов и петель алгоритм работает аналогично; нужно хранить идентификаторы рёбер, чтобы помечать их один раз.
Неэффективные альтернативы
- Алгоритм Флёри (всегда выбирать любое допустимое ребро, не мост, если возможно) корректен, но требует проверки мостов много раз → в худшем случае $O(|E{|}^2)$.
Особенности для очень больших графов
- Проблемы: оперативная память ($O(|V|+|E|)$) и произвольный доступ к спискам смежности; необходимость хранить и помечать каждое ребро; операции ввода-вывода при вычислениях на диске.
- Подходы и рекомендации:
- Внешняя память: хранить списки рёбер на диске в виде последовательных блоков, делать один проход для постройки локальных туров; затем склеивать локальные туры (внешне-памятная вариация Hierholzer). I/O-сложность близка к сложности сортировки/сканирования списка рёбер.
- Разделение/распараллеливание: разбить граф по ребрам на блоки, в каждом блоке найти локальные эйлеровы туры, затем объединять через граничные вершины (потребует обмена и согласования данных). Фреймворки: Pregel/GraphX/MapReduce-решения возможны, но реализация нетривиальна.
- Потоковая обработка: если граф — поток рёбер, можно сначала сгруппировать рёбра по вершинам (внешняя сортировка) для построения списков смежности, затем применить Hierholzer на внешней памяти.
- Сжатие/битовые структуры: хранить флаги использования рёбер в битсетах, использовать CSR-подобные структуры для компактности.
- Отказ от полного построения: в некоторых задачах достаточно проверять условие существования (степени и связность компонент с ненулевой степенью) — это дешевле: подсчёт степеней — один проход по рёбрам, проверка связности — DFS/BFS по диску или по выборке.
- Практический совет: для очень больших графов сначала проверить критерии (степени, связность компонент с ненулевой степенью). Если критерии выполнены и нужно явное эйлерово представление — применять внешнюю/распределённую реализацию Hierholzer с хранением рёбер и меток в устойчивом хранилище; учитывать стоимость I/O и балансировку по диапазонам вершин.
Краткое резюме
- Необходимое и достаточное условие: связность на вершинах с ненулевой степенью и число нечётных вершин равно $0$ (цикл) или $2$ (путь).
- Построение: Hierholzer — линейное по числу рёбер, на практике хранить идентификаторы рёбер и списки смежности.
- Для очень больших графов требуются внешняя память, распределённые/параллельные алгоритмы или сжатые структуры; проверка условий (степени и связность) выполняется гораздо проще, чем построение полного маршрута.