Ейлеровим циклом (також відомий як Ейлерів ланцюг) називається замкнутий маршрут, в якому кожне ребро графа зустрічається точно один раз. Для існування такого маршруту в зв’язному неорієнтованому графі необхідно і достатньо, щоб степінь для всіх його вершин була парною. Сьогодні, розглянемо алгоритм, основна ідея якого збігається з алгоритмом обходу графа в глибину, та з його допомогою, для деякого неорієнтований граф , знайдемо Ейлерів цикл. Для цього, припустимо, що вимога зв’язності і парності степенів для нього виконується. Відмітимо, що в такому випадку граф є, принаймі, двозв’язним а отже, містить цикл.
Графічне представлення алгоритму пошуку Ейлерового циклу
Отже, для побудови Ейлерового циклу довільно виберемо одну з вершин графа , наприклад вершину
. На наступному кроці, виберемо будь-яке з інцидентних даній вершині ребер, наприклад
, і з його допомогою перейдемо у відповідну суміжну вершину. Ребро
після виконання цих дій, вважатиметься пройденим. Після цього, повторюємо цю операцію, щоразу обираючи нове ребро, поки не опинимося в вихідній вершині
і не замкнемо цикл.
Позначимо знайдений таким чином цикл як . Якщо
включає всі ребра графа
, то Ейлерів цикл побудовано. В іншому випадку, переходимо до розгляду графа
, який отримуємо шляхом видалення з графа
всіх ребер, що входять до графу
. Цей граф може бути як зв’язним, так і не зв’язним, але будь-яка його компонента в силу зв’язності
має хоча б одну загальну вершину з графом
. Так як кожна вершина в
і
має парну степінь, то і в
степінь всіх вершин повинна бути парною.
Нехай загальна вершина
і
, яка не є ізольованою в графі
. Знайдемо в
цикл, що містить цю вершину, і позначимо його як
. Після цього, об’єднаємо цикл
і
, згідно з наступним правилом:
Далі, знову-таки, перевіряємо чи отриманий цикл не являється Ейлеровим. Ящо так, то процес завершено. В іншому випадку слід перейти до розгляду графа
(отримуємо шляхом видалення з графа
всіх ребер, що входять до графа
), відшукати в ньому цикл
, який слід об’єднати з
і так далі. Відмітимо, що виходячи з того, що кожен раз кількість не пройдених ребер зменшується, то описаний процес скінченний і повинен закінчитися побудовою Ейлерового циклу.
Зауваження: головна відмінність розглядуваного алгоритму від пошуку в глибину полягає в тому, що як пройдені позначаються саме ребра, а не вершини. Тому одна і та ж вершина може відвідувати кілька разів, але кожне ребро проходиться не більше одного разу, так що в отриманому маршруті ребра не повторюватимуться.
Пошук Ейлерового циклу в неорієнтованому графі – приклад:
Побудувати Ейлерів цикл для неорієнтованого графа наступного вигляду.
Неорієнтований граф задачі
Проаналізувавши заданий граф бачимо, що кожна з його вершина має парну степінь, тому цей граф Ейлерів, а отже містить Ейлерів цикл. Застосуємо для нього розглянутий вище алгоритм. Для цього, на першому кроці, виберемо в якості початкової вершину номер «1», та скориставшись одним з не пройдених інцидентних їй ребер, наприклад , переходимо у вершину номер «2». Ребро
після цього вважається пройденим. Після цього, скориставшись не пройденим інцидентним ребер, але на цей раз для вершини «2», переходимо у вершину «3». Продовжуючи аналогічні дії далі, отримаємо список вершин, послідовний обхід яких і утворюватиме для заданого графа наступний Ейлерів ланцюг:
.