Побудова Ейлерового циклу в неорієнтованому графі використовуючи алгоритм Флері

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

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

algorytm_fleri5

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

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

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

Нехай потрібно знайти Ейлеров цикл в неорієнтованому графі, представленому на наступному малюнку.

Алгоритм Флері - приклад

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

Безпосередньою перевіркою переконуємося, що степеня усіх вершин парні, тобто заданий граф Ейлерів. В якості початкової вершини виберемо вершину номер «1». На першій ітерації перейдемо в будь-яку сімужну початковій вершині, наприклад, у вершину «2» і видалимо, при цьому, ребро . На другій ітерації, перейдемо у вершину «3» і видалимо ребро . Після цього, знову-таки попадаємо у вершину «1», видаляючи після цьому ребро . Продовжуючи ітераційни процес далі, переходиму у вершини «4»«2»«7»«6»«4»«3»«5»«1» видаляючи при цьому насиупні ребра та .

algorytm_fleri2

Побудова Ейлерового циклу використовуючи алгоритм Флері

Далі, слідуючи порядку в якому були пройдені ребра, отримаємо Ейлерів цикл наступного вигляду: .

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

Алгоритм Флері блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар