Кратко. Сначала — необходимые общие условия, затем классические достаточные критерии (теоремы), потом практическая эвристика для построения цикла.
Необходимые условия
- Для любого вершины $v$ по крайней мере одно входящее и одно исходящее ребро: ${\mathrm{deg}}^{+}(v)\ge 1,{\mathrm{deg}}^{-}(v)\ge 1$ (для $n>1$).
- Суммы степеней согласованы: ${\sum }_v{\mathrm{deg}}^{+}(v)={\sum }_v{\mathrm{deg}}^{-}(v)=m$ (число дуг).
- Если для всех вершин ${\mathrm{deg}}^{+}(v)={\mathrm{deg}}^{-}(v)=1$, то гамильтонов цикл существует тогда и только тогда, когда орграф состоит из одной ориентированной циклической компоненты (в противном случае это покрытие циклов).
Утверждения-«достаточники» (быстрые критерии, дающие гарантию)
- Теорема Гуайла‑Хури (Ghouila‑Houri): Если орграф на $n$ вершинах удовлетворяет для каждой вершины ${\mathrm{deg}}^{+}(v)+{\mathrm{deg}}^{-}(v)\ge n$, то в нём есть ориентированный гамильтонов цикл.
- Следствие: достаточно, чтобы ${\delta }^{+}(D)\ge n/2$ и ${\delta }^{-}(D)\ge n/2$.
- Есть также «Ore‑типы» условий для орграфов (теоремы Вудалла и др.): например, если для любой пары вершин $x,y$ такой, что дуги $x\to y$ нет, выполняется ${\mathrm{deg}}^{+}(x)+{\mathrm{deg}}^{-}(y)\ge n$, то цикл существует. (Эти условия — достаточные, не необходимые.)
Проверка реализуемости заданных вход/выход-степеней
- Пары последовательностей $(r_i)$ (out‑степени) и $(s_i)$ (in‑степени) являются реализуемыми как простой орграф тогда и только тогда, когда $\sum r_i=\sum s_i$ и выполняется критерий типа Gale / Fulkerson–Chen–Anstee (т.е. набор неравенств для подмножеств вершин). (Это критерий диграфичности.)
Сложные случаи — эвристика построения гамильтонова цикла
(учитывая, что задача NP‑полна, в общем случае точного многополиномиального алгоритма нет)
Базовый план эвристики (рабочая последовательность действий)
1. Построить покрытие вершин ориентированными циклами (директ 1‑фактор, cycle cover): это задача назначений (перестановка). Можно найти любая такая перестановка алгоритмом максимального соответствия/венгером. Результат — набор циклов, покрывающих все вершины.
2. Пока покрытие содержит более одного цикла, пытаться «сливать» циклы:
- Ищите две разные цикловые компоненты $C_1,C_2$ и вершины $u\in C_1,v\in C_2$ такие, что существуют дуги $u\to x$ с $x\in C_2$ и $y\to v$ с $y\in C_1$. Тогда можно выполнить 2‑перестановку: заменить дуги $(u\to u^{\prime })$ и $(y\to v)$ на $(u\to v)$ и $(y\to u^{\prime })$, что соединит циклы. Формально: заменить пару $(u\to u^{+}),(y\to v)$ на $(u\to v),(y\to u^{+})$ при наличии этих дуг. Повторять.
- Если прямых пар нет, искать последовательности перестановок (цепочку замен), т.е. строить ориентированный граф компонент (вершины = циклы, ребро = наличие дуги из одного цикла в другой) и искать циклы в этом сверхграфе, которые позволяют выполнить серию обменов и объединить несколько компонент.
3. Применять метод «rotation‑extension» (адаптация Pósa): поддерживать длинную ориентированную простую путь $P$ и пробовать «повороты» концов пути, заменяя последовательно дуги, чтобы освободить новые продолжения; если удаётся замкнуть путь в цикл, проверить, является ли он гамильтоновым, иначе продолжать расширять.
4. При застревании использовать локальные операторы улучшения: 2‑оп/3‑оп обмены дуг (аналог TSP‑операций), поиск кратчайших путей между циклами, использование max‑flow / matching для нахождения нужных перестановок между предшественниками и наследниками.
5. Комбинации со случайными рестартами: повторять шаги 1–4 с разными случайными исходными покрытием или случайным приоритетом вершин; сохранять лучший (или успешный) результат.
6. В трудных инстанциях формализовать задачу как SAT/ILP (переменные $x_{uv}\in \{0,1\}$ для дуг $u\to v$ с ограничениями «вход = выход =1» и подсказками для связности) и решать оптимизатором/солвером — часто даёт решение при умеренных размерах.
Практические замечания и эвристические приоритеты
- Начинать с жадного расширения длинного пути из вершины с малого резерва (малые ${\mathrm{deg}}^{+}$ или ${\mathrm{deg}}^{-}$) — это уменьшает вероятность «запереть» вершину.
- Отдавать приоритет объединению маленьких циклов сначала (легче найти мосты).
- Использовать структуры данных для быстрого поиска дуг между циклами (хэш/списки соседей).
- Для больших графов комбинировать многократные рестарты + локальный поиск; для средних — ILP/SAT.
Заключение
- Для гарантии существования смотрите теорему Гуайла‑Хури и родственные достаточные условия.
- На практике: получить покрытие циклов (assignment), затем последовательно сливать циклы через простые 2‑перестановки и более сложные цепочки обменов; при трудностях — комбинировать с локальными операторами, случайными рестартами или ILP/SAT‑решением.