Кратко, по пунктам.
Критерии существования
- Неориентированный связный граф:
- Эйлеров цикл (замкнутый эйлеров путь) существует тогда и только тогда, когда для каждой вершины степень чётна: $\forall v:\mathrm{deg}(v)$ — чётна.
- Эйлеров путь (трейл, не обязательно замыкающийся) существует тогда и только тогда, когда число вершин нечётной степени равно $0$ или $2$. Если равно $2$, то путь начинается и кончается в этих двух вершинах.
- Ориентированный связный граф:
- Эйлеров цикл существует тогда и только тогда, когда для каждой вершины $\mathrm{indeg}(v)=\mathrm{outdeg}(v)$ и все вершины с ненулевой степенью лежат в одной сильно связной компоненте (или более формально: ориентированный граф с удалёнными нулевыми вершинами должен быть сильно связен).
- Эйлеров путь (трейл) существует тогда и только тогда, когда граф слабосвязан (если считать рёбра неориентированными все вершины с ненулевой степенью связаны), и либо $\forall v:\mathrm{indeg}(v)=\mathrm{outdeg}(v)$ (это даёт цикл), либо ровно одна вершина имеет $\mathrm{outdeg}=\mathrm{indeg}+1$ (старт), ровно одна — $\mathrm{indeg}=\mathrm{outdeg}+1$ (финиш), все остальные — $\mathrm{indeg}=\mathrm{outdeg}$.
Критерии существования гамильтонова пути/цикла
- Нет простого необходимого и достаточного критерия, проверяемого за полиномиальное время (задача NP-полна).
- Существуют достаточные условия:
- Теорема Дирака: если $n\ge 3$ и минимальная степень $\delta (G)\ge n/2$, то граф содержит гамильтонов цикл.
- Теорема Оре: если для любых двух несмежных вершин $u,v$ выполнено $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$, то есть гамильтонов цикл.
- Но общая задача «существует ли гамильтонов путь/цикл?» — NP-полна.
Алгоритмы поиска
- Эйлеров путь/цикл (Hierholzer):
- Идея: пройти по рёбрам, пока возможно, возвращаясь к вершине; если остались неиспользованные рёбра, вставить в текущий цикл дополнительные подциклы.
- Псевдокод (неориентированный):
1. Найти стартовую вершину: если есть 2 вершины нечётной степени — старт из одной из них, иначе любую.
2. Выполнять стековый проход: идти по любому неиспользованному ребру, помечать его использованным, добавлять вершины в стек; когда из вершины нет неиспользованных рёбер — вынимать её в ответ (формируется обратный порядок).
3. Полученный последовательный список вершин — эйлеров путь/цикл.
- Сложность: $O(m)$ по времени и $O(m)$ по памяти, где $m$ — число рёбер. (Аналогично для ориентированного графа, учитываются indeg/outdeg.)
- Гамильтонов путь/цикл:
- Полный перебор (backtracking / DFS) с проверкой посещения: простая реализация в худшем случае имеет факториальную сложность $O(n!)$.
- Динамическое программирование (Held–Karp) для поиска гамильтонова цикла/пути:
- DP по подмножествам: $dp[S][v]$ — правда ли, что существует путь, проходящий через вершины множества $S$ и оканчивающийся в $v$.
- Переходы: $dp[S\cup \{u\}][u]\leftarrow \exists v\in S:dp[S][v]$ и $(v,u)\in E$.
- Сложность: время $O(n^2{2}^n)$, память $O(n{2}^n)$.
- Эвристики и приближённые/частные алгоритмы: ветвление с отсечениями, алгоритмы на конкретных классах графов, SAT/ILP редукции, метаэвристики.
- Замечание: если требуется просто решить задачу в общем случае, единственно гарантированные алгоритмы — экспоненциальные (за исключением специальных классов графов, где есть полиномиальные критерии).
Различия в вычислительной сложности (кратко)
- Поиск эйлерова пути: полиномиальная сложность — линейное время $O(m)$. Причина: локальные условия по степеням дают необходимое и достаточное условие и маршрут строится жадно.
- Поиск гамильтонова пути: NP-полная задача → нет известного алгоритма за полиномиальное время (при общепринятой гипотезе $P\ne NP$). Лучшие точные алгоритмы требуют экспоненциального времени (например, Held–Karp $O(n^2{2}^n)$ или в худшем $O(n!)$ для наивного перебора).
Если нужно, могу привести короткие реализации (псевдокод) для Hierholzer и для Held–Karp.