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

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

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

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

2°. Рассмотрим подграф G ₁(X, E\ m₁). Возьмем в качестве e ₂ ребро, инци­дентное вершине x ₁ и неинцидентное вершине a, которое также не является мостом в подграфе G ₁ (если такое ребро e ₂ существует!). Получим простую цепь m₂ = { e ₁, e ₂}.

3°. Пусть e ₂ = (x ₁, x ₂), x ¹ a. Рассмотрим подграф G ₂(X, E\ m₂) и удалим из него все изо­лированные вер­шины. В полученном подграфе выберем ребро e ₃Î E\ m₂, инцидентное вершине a, которое не является мостом в под­графе (если такое ребро e ₃ суще­ству­ет!). Получим простую цепь

m₃ = { e ₁, e ₂, e ₃}.

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

Дата добавления: 2014-01-06