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

В предыдущем разделе был установлен эффективный способ проверки наличия эйлерова цикла в графе. А именно, для этого необходимо и достаточно убедиться, что степени всех вершин четные, что нетрудно сделать при любом представлении графа. Следующий алгоритм находит эйлеров цикл в графе, если известно, что граф эйлеров.

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

Вход: эйлеров граф G(V, Е), заданный списками смежности (Г[г>] — список вершин, смеж­ных с вершиной v).

Выход: последовательность вершин эйлерова цикла. S: = 0 { стек для хранения вершин } select v G V { произвольная вершина } v —> S { положить v в стек S } while S ф 0 do

v <r- S;v —> S {v — верхний элемент стека } if Г>] = 0 then v 4- 5; yield v else

select u € T[v] { взять первую вершину из списка смежности } и —¥ S { положить и в стек }

1>]: = 1>] \ {и}; Г [и]: = Г [и] \ {v} { удалить ребро (v, и) } end if end while

обоснование

Принцип действия этого алгоритма заключается в следующем. Начиная с произ­ вольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке 5. Заметим, что при этом степени всех вершин остались четными. Далее вершина v выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.