Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
==Алгоритм построения эйлерова цикла, эйлерова пути==
Запускаем алгоритм от вершины <tex>v</tex>.
Алгоритм будет корректно работать, когда в графе существует эйлеров цикл, то есть степени всех вершин четны.
FindEulerPath(v)
перебираем все рёбра, выходящие из вершины v.
каждое такое ребро удаляем из графа.
вызываем FindEulerPath из второго конца этого ребра.
добавляем вершину v в ответ.
Сложность алгоритма <tex>O(E)</tex>
В случае не существования эйлерова цикла, соединим вершины с нечетной степенью ребром, найдем эйлеров цикл, а затем удалим добавленное ребро из ответа.
==Полезные ссылки==
