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

 

Для начала отметим, что теорема 7.1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.

Пусть G(X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.

1°. Пусть a — произвольная вершина графа G. Возьмем любое ребро e1=(a, x1) , инцидентное вершине a, и положим m = {e1}.

2°. Рассмотрим подграф G1(X, E\m1). Возьмем в качестве e2 ребро, инци­дентное вершине x1 и неинцидентное вершине a, которое также не является мостом в подграфе G1 (если такое ребро e2 существует!). Получим простую цепь m2 = {e1, e2}.

3°. Пусть e2 = (x1, x2), x ¹ a. Рассмотрим подграф G2(X, E\m2) и удалим из него все изо­лированные вер­шины. В полученном подграфе выберем ребро e3ÎE\m2, инцидентное вершине a, которое не является мостом в под­графе (если такое ребро e3 суще­ству­ет!). Получим простую цепь

m3 = {e1, e2, e3}.

Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл m = {e1, e2, …, en}, где n — число ребер графа G(X, E).