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

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

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

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

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

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

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

Зауваження: головна відмінність розглядуваного алгоритму від пошуку в глибину полягає в тому, що як пройдені позначаються саме ребра, а не вершини. Тому одна і та ж вершина може відвідувати кілька разів, але кожне ребро проходиться не більше одного разу, так що в отриманому маршруті ребра не повторюватимуться.

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

Побудувати Ейлерів цикл для неорієнтованого графа наступного вигляду.

Неорієнтований граф задачі

Проаналізувавши заданий граф бачимо, що кожна з його вершина має парну степінь, тому цей граф Ейлерів, а отже містить Ейлерів цикл. Застосуємо для нього розглянутий вище алгоритм. Для цього, на першому кроці, виберемо в якості початкової вершину номер «1», та скориставшись одним з не пройдених інцидентних їй ребер, наприклад , переходимо у вершину номер «2». Ребро  після цього вважається пройденим. Після цього, скориставшись не пройденим інцидентним ребер, але на цей раз для вершини «2», переходимо у вершину «3». Продовжуючи аналогічні дії далі, отримаємо список вершин, послідовний обхід яких і утворюватиме для заданого графа наступний Ейлерів ланцюг: .

Побудова Ейлерового циклу для неорієнтованого графа

Блок-схема алгоритму пошуку Ейлерового циклу в неорієнтованому графі