Пошук Ейлерового циклу в неорієнтованому графі

Ейлеровим циклом (також відомий як Ейлерів ланцюг) називається замкнутий маршрут, в якому кожне ребро графа зустрічається точно один раз. Для існування такого маршруту в зв'язному неорієнтованому графі необхідно і достатньо, щоб степінь для всіх його вершин була парною. Сьогодні, розглянемо алгоритм, основна ідея якого збігається з алгоритмом обходу графа в глибину, та з його допомогою, для деякого неорієнтований граф , знайдемо Ейлерів цикл. Для цього, припустимо, що вимога зв'язності і парності степенів для нього виконується. Відмітимо, що в такому випадку граф є, принаймі, двозв'язним а отже, містить цикл.

poshuk_ejlerovogo_shljahu_v_grafi18

Графічне представлення алгоритму пошуку Ейлерового циклу

Отже, для побудови Ейлерового циклу довільно виберемо одну з вершин графа , наприклад вершину . На наступному кроці, виберемо будь-яке з інцидентних даній вершині ребер, наприклад , і з його допомогою перейдемо у відповідну суміжну вершину. Ребро  після виконання цих дій, вважатиметься пройденим. Після цього, повторюємо цю операцію, щоразу обираючи нове ребро, поки не опинимося в вихідній вершині  і не замкнемо цикл.

Читати повністю