Эйлеров цикл (путь-цикл)

Эйлеров цикл — это замкнутый маршрут в графе, который проходит по каждому ребру ровно один раз и возвращается в начальную вершину. Похожее понятие — эйлеров путь (иногда говорят «путь-цикл»), — это маршрут, которому не обязательно быть замкнутым, но он также проходит по всем ребрам ровно один раз. Эти понятия важны для задач о прокладке маршрутов, уборке улиц, распаковке и сборке генетических последовательностей и других практических задач, где необходимо обойти все связи без повторений.

Классические критерии существования эйлерова цикла отличаются для неориентированных и ориентированных графов и сводятся к проверке степеней вершин и связности. Для неориентированного графа достаточно того, чтобы оставшийся после удаления изолированных вершин граф был связен и выполнялось условие: \(\forall v\in V\ \big(\deg(v)\equiv 0\pmod{2}\big)\). Если же требуется найти просто эйлеров путь (необязательно замкнутый), то вместо этого выполняется более мягкое условие: \(\big|\{v\in V:\ \deg(v)\text{\ — нечётна}\}\big|\in\{0,2\}\). Для ориентированных графов ключевым требованием служит равенство входящих и выходящих степеней каждой вершины при условии сильной или соответствующей связности: \(\forall v\in V\ \big(d^{+}(v)=d^{-}(v)\big)\). На практике эти критерии позволяют быстро сказать, возможен ли обход всех ребер без повторов, и выбрать подходящий алгоритм (например, алгоритм Гиршельца — Hierholzer) для построения самого цикла или пути.

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