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