4.6.2 Алгоритм Флёри нахождения эйлерова цикла

Естественно возникает вопрос: как найти хотя бы один эйлеров цикл в эйлеровом графе, пройдя по каждому ребру один раз и вернуться в начало.

2

3

1

4

6

5

Рисунок 4.22 – Граф с эйлеровым циклом

Указание эйлерова цикла равносильно выдаче некоторой нумерации ребер графа, соответствующей порядку их обходав цикле, проходящем через все ребра.

Нахождение эйлерова цикла в графе можно осуществить с помощью алгоритма Флёри:

1. Начиная с произвольной вершины х₀ исходного графа Г₀, присваиваем любому инцидентному ей ребру (х₀, х₁) номер 1. Удаляем ребро (х₀, х₁) из множества ребер графа Г₀ , получая граф Г₁ . Переходим в следующую вершину х₁.

2. Пусть х_k — вершина, в которую мы пришли после очередного шага нумерации ребра, получившего номер k. Для дальнейшей нумерации выбираем любое ребро графа Г_k, инцидентное вершине х_k, с учетом следующего правила: ребра, удаление которых из графа Г_k повлечет нарушение его связности, выбираются только тогда, когда другой выбор осуществить нельзя.

3. Алгоритм заканчивает свою работу, когда получен цикл, т.е. выбрано ребро (х, х₀), где х - некоторая вершина графа Г₀.

Иначе – повторяем пункт 2.