Эйлеров цикл

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)

Граф Кёнигсбергских мостов. Этот граф не является полуэйлеровым, поэтому решения не существует

Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл

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

Полуэйлеров граф — граф, в котором существует эйлеров путь.

Эйлеров граф — граф, в котором существует эйлеров цикл.

Существование эйлерова цикла и эйлерова путиПравить

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

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

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

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

Ориентированный граф $G=(V,A)$$G=(V,A)$  содержит эйлеров цикл тогда и только тогда, когда он сильно связан или среди его компонент сильной связности только одна содержит ребра (а все остальные являются изолированными вершинами) и для каждой вершины графа её входящая степень $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}(\cdot <!--\; \cdot \; -->)$${\mathrm {indeg}}(\cdot )$  равна её исходящей степени $\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}(\cdot <!--\; \cdot \; -->)$${\mathrm {outdeg}}(\cdot )$ , то есть в вершину входит столько же ребер, сколько из неё и выходит: $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}(v)=\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}(v)\mathrm{\forall <!--\; \forall \; -->}v\in <!--\; \in \; -->V$${\mathrm {indeg}}(v)={\mathrm {outdeg}}(v)\quad \forall v\in V$ .

Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф $G=(V,A)$$G=(V,A)$  содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф $G=(V,A)$$G=(V,A)$  содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда он слабо связен и существуют две вершины $p\in <!--\; \in \; -->V$$p\in V$  и $q\in <!--\; \in \; -->V$$q\in V$  (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}(q)=\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}(q)+1$${\mathrm {indeg}}(q)={\mathrm {outdeg}}(q)+1$  и $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}(p)=\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}(p)-<!--\; -\; -->1$${\mathrm {indeg}}(p)={\mathrm {outdeg}}(p)-1$ , а все остальные вершины имеют одинаковые полустепени исхода и захода: $\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{d}\mathrm{e}\mathrm{g}(v)=\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}(v)\mathrm{\forall <!--\; \forall \; -->}v\in <!--\; \in \; -->V\setminus <!--\; \setminus \; -->\{p,q\}$${\mathrm {outdeg}}(v)={\mathrm {indeg}}(v)\quad \forall v\in V\setminus \{p,q\}$ .

Поиск эйлерова пути в графеПравить

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

Поиск эйлерова цикла в графеПравить

Алгоритм ФлёриПравить

Основной источник: M. Fleury. Deux problèmes de Géométrie de situation (фр.) // Journal de mathématiques élémentaires [et spéciales]. — Paris: C. Delagrave, 1883. — Vol. 2, livr. 2nd ser.. — P. 257–261.

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

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

Этот алгоритм неэффективен: время работы оригинального алгоритма O(|E|²). Если использовать более эффективный алгоритм для поиска мостов, то время выполнения можно снизить до $O(|E|(\log <!--\; \; -->|E|{)}^3\log <!--\; \; -->\log <!--\; \; -->|E|)$$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(|E|), то есть линейная относительно количества рёбер в данном графе.

См. такжеПравить

• Гамильтонов цикл
• Граф (математика)
• Задача о ходе коня
• Дискретная математика
• Проблема семи мостов Кёнигсберга
• Список объектов, названных в честь Леонарда Эйлера

СсылкиПравить

• Реализация алгоритма поиска эйлерова цикла (краткие описания и программы на C++)
• Реализация алгоритма поиска эйлерова цикла на codenet.ru
• Теория графов и комбинаторика
• Графы. Циклы и разрезы (ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, Визуализаторы)
• Е. Гик. «Шахматы и математика» Конь-хамелеон
• Weisstein, Eric W. Eulerian Circuit (англ.) на сайте Wolfram MathWorld.