double arrow

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

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

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

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

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

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

m3 = { e 1, e 2, e 3}.

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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: