WikiSort.ru - Не сортированное

В неориентированном графе

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

Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени.^[1][2] Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть четным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.

В ориентированном графе

Ориентированный граф ${\displaystyle G=(V,A)}$ содержит эйлеров цикл тогда и только тогда, когда он сильно связан или среди его компонент сильной связности только одна содержит ребра (а все остальные являются изолированными вершинами) и для каждой вершины графа её входящая степень ${\displaystyle \mathrm {indeg} (\cdot )}$ равна её исходящей степени ${\displaystyle \mathrm {outdeg} (\cdot )}$ , то есть в вершину входит столько же ребер, сколько из неё и выходит: ${\displaystyle \mathrm {indeg} (v)=\mathrm {outdeg} (v)\quad \forall v\in V}$ .

Так эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф ${\displaystyle G=(V,A)}$ содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющейся циклом. Ориентированный граф ${\displaystyle G=(V,A)}$ содержит эйлеров путь, не являющейся циклом, тогда и только тогда, когда существуют две вершины ${\displaystyle p\in V}$ и ${\displaystyle q\in V}$ (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами ${\displaystyle \mathrm {indeg} (q)=\mathrm {outdeg} (q)+1}$ и ${\displaystyle \mathrm {indeg} (p)=\mathrm {outdeg} (p)-1}$ , а все остальные вершины имеют одинаковые полустепени исхода и захода: ${\displaystyle \mathrm {outdeg} (v)=\mathrm {indeg} (v)\quad \forall v\in V\setminus \{p,q\}}$ ^[3].

Алгоритм Флёри

Алгоритм был предложен Флёри в 1883 году.

Пусть задан граф ${\displaystyle G=(V,E)}$ . Начинаем с некоторой вершины ${\displaystyle p\in V}$ и каждый раз вычеркиваем пройденное ребро. Не проходим по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин), т.е. необходимо проверять, является ли ребро мостом или нет.

Этот алгоритм неэффективен: время работы оригинального алгоритма O(|E|²). Если использовать более эффективный алгоритм для поиска мостов^[4], то время выполнения можно снизить до ${\displaystyle O(|E|(\log |E|)^{3}\log \log |E|)}$ , однако это всё равно медленнее, чем другие алгоритмы.

Алгоритм может быть распространен на ориентированные графы.

Алгоритм на основе циклов

Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.

Реализовать это можно, например, так, рекурсивно:

procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его
    добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода)
    удаляем цикл из графа
2. идем по элементам массива cycles
    каждый элемент cycles[i] добавляем к ответу
    из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])

Достаточно вызвать эту процедуру из любой вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.

Для поиска цикла на шаге 1 используем поиск в глубину.

Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.