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

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

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

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

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

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

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

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

Обоснование алгоритма

Предположим, что уже построена простая цепь _k-1= {e₁,e₂, …,e_k-1} дляk2 методом, указанным в алгоритме. Пустьe_k-1= (x_k-2,x_k-1) иx_k-1a. Рас­смо­трим подграф, который получается из подграфаG_k-1(X,E\_k-1) удалением всех изолированных вершин. Вершинаx_k-1в этом подграфеимеет нечет­ную степень, поэтому существует по крайней мере одно реброe_kE\_k-1, ин­ци­дентноеx_k-1. Если это ребро единственное, то оно не является мостом в графе. В противном случае вершинаaбудет связана с некоторой вер­ши­нойединственной цепью, содержащей реброe_k, что противоречит суще­ствованию эйлерова цикла в графеG. Посколькуe_k- не мост, то процесс мож­но продолжать, взяв. Если реброe_kне единственное инци­дентное вершинеx_k-1, то среди этих ребер есть по крайней мере одно, не явля­ющееся мостом. В противном случае один из этих мостовможно выбро­сить так, что вершиныx_k-1иaпопадут в разные компоненты связности графа. Еслиx_k-1принадлежит компонентеM, то в этой компоненте все вер­шины имеют четную степень, поэтому существует эйлеров цикл вM, про­хо­дящий черезx_k-1. Этот цикл содержит все ребра, инцидентныеx_k-1и при­над­лежащие, являющиеся одновременно мостами. Получено противоречие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует реброe_k, инцидентное вершинеx_k-1и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв

.

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершиныaотносительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл- простой цикл. Покажем, чтосодержит все ребра графаG. Если не все ребра графаGпринадлежат, то не принадлежащиеребра порождают компоненты связностиC₁, …,C_m(m1) в подграфе. Пусть компонентаC_i, 1imсоединяется с цикломв вершинеy_i. Если существует реброe, такое, чтоe=(y_i,a), то при построении циклабыло нарушено правило выбора ребраe, что невозможно. Если часть цикла, соединяющаяy_iиa, состоит более чем из одного ребра, то первое ребро этой частибыло мостом, и поэтому было нарушено правило вы­бора, что невозможно. Итак, непройденных ребер быть не может, поэ­тому- эйлеров цикл.