Алгоритм Флери построения эйлерова цикла

Установив , что данный граф эйлеров, построим в нем какой-нибудь эйлеров цикл. Для этого нужно указать очередность обхода ребер в цикле, присвоив им соответствующие порядковые номера. Решить такую задачу позволяет алгоритм Флери, который заключается в следующем:

1. Начиная с произвольной вершины s, присваиваем произвольному ребру {s,v} номер 1. Исключаем это ребро из дальнейшего рассмотрения (вычеркиваем) и переходим в вершину v.
2. Пусть на очередном шаге мы пришли в некоторую вершину w, присвоив какому-то ребру {v,w} номер k. Среди еще непронумерованных ребер, инцидентных w, выбираем любую; при этом мост выбираем только в том случае, когда нет других возможностей; присваиваем выбранному  ребру номер k+1, вычеркиваем это ребро.

Заканчивается выполнение алгоритма, когда все ребра данного графа пронумерованы.

Далее приведено обоснование алгоритма Флери.

Теорема 9. Алгоритм Флери позволяет построить эйлеров цикл, если такой цикл существует в данном графе.