Дан граф найти Эйлеров цикл

Для поиска Эйлерова цикла в графе необходимо следовать алгоритму, известному как алгоритм Флёри или использовать более эффективный метод на основе поиска в глубину.

Эйлеров цикл (или Эйлеров путь) существует в графе, если и только если граф является связным и все вершины имеют четную степень (для неориентированных графов). В данном случае граф ориентированный, и Эйлеров цикл существует, если из каждой вершины выходит столько же рёбер, сколько и входит.

Проверим выполнение этих условий для данного графа:

Проверка связности: Убедимся, что можно попасть из одной вершины в любую другую, следуя рёбрам в любом направлении.
Проверка степени вершин: Для каждой вершины проверим, что количество входящих рёбер равно количеству исходящих рёбер.
Алгоритм Флёри:
Начать с любой вершины (в случае Эйлерова цикла, начальная вершина не имеет значения).
Следовать рёбрам по правилу: выбираем ребро так, чтобы удаление этого ребра не разорвало граф на части, за исключением случая, когда это единственное доступное ребро.
Повторять шаг 2 до тех пор, пока все рёбра не будут использованы.
Теперь выполним алгоритм Флёри для данного графа:

Начальная вершина: Выберем вершину 0.

Проверка и следование рёбрам:

Из вершины 0 выбираем ребро (0, 1) и переходим в вершину 1.
Из вершины 1 выбираем ребро (1, 5) и переходим в вершину 5.
Из вершины 5 выбираем ребро (5, 6) и переходим в вершину 6.
Из вершины 6 выбираем ребро (6, 2) и переходим в вершину 2.
Из вершины 2 выбираем ребро (2, 0) и переходим в вершину 0.
Из вершины 0 выбираем ребро (0, 3) и переходим в вершину 3.
Из вершины 3 выбираем ребро (3, 4) и переходим в вершину 4.
Из вершины 4 выбираем ребро (4, 5) и переходим в вершину 5.
Из вершины 5 выбираем ребро (5, 10) и переходим в вершину 10.
Из вершины 10 выбираем ребро (10, 9) и переходим в вершину 9.
Из вершины 9 выбираем ребро (9, 13) и переходим в вершину 13.
Из вершины 13 выбираем ребро (13, 11) и переходим в вершину 11.
Из вершины 11 выбираем ребро (11, 12) и переходим в вершину 12.
Из вершины 12 выбираем ребро (12, 8) и переходим в вершину 8.
Из вершины 8 выбираем ребро (8, 4) и переходим в вершину 4.
Из вершины 4 выбираем ребро (4, 7) и переходим в вершину 7.
Из вершины 7 выбираем ребро (7, 11) и переходим в вершину 11.
Из вершины 11 выбираем ребро (11, 6) и переходим в вершину 6.
Из вершины 6 выбираем ребро (6, 3) и переходим в вершину 3.
Из вершины 3 выбираем ребро (3, 7) и переходим в вершину 7.
Из вершины 7 выбираем ребро (7, 8) и переходим в вершину 8.
Из вершины 8 выбираем ребро (8, 12) и переходим в вершину 12.
Из вершины 12 выбираем ребро (12, 13) и переходим в вершину 13.
Из вершины 13 выбираем ребро (13, 10) и переходим в вершину 10.
Из вершины 10 выбираем ребро (10, 6) и переходим в вершину 6.
Из вершины 6 выбираем ребро (6, 5) и переходим в вершину 5.
Из вершины 5 выбираем ребро (5, 1) и переходим в вершину 1.
Из вершины 1 выбираем ребро (1, 2) и переходим в вершину 2.
Из вершины 2 выбираем ребро (2, 4) и переходим в вершину 4.
Из вершины 4 выбираем ребро (4, 0) и возвращаемся в начальную вершину 0.
Итак, мы нашли Эйлеров цикл:

 0 -> 1 -> 5 -> 6 -> 2 -> 0 -> 3 -> 4 -> 5 -> 10 -> 9 -> 13 -> 11 -> 12 -> 8 -> 4 -> 7 -> 11 -> 6 -> 3 -> 7 -> 8 -> 12 -> 13 -> 10 -> 6 -> 5 -> 1 -> 2 -> 4 -> 0. 
 

Этот маршрут проходит через каждое ребро графа ровно один раз и возвращается в исходную вершину.