Русская Википедия:Эйлеров цикл
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Полуэйлеров граф — граф, в котором существует эйлеров путь.
Эйлеров граф — граф, в котором существует эйлеров цикл.
Существование эйлерова цикла и эйлерова пути
В неориентированном графе
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный или будет являться связным, если удалить из него все изолированные вершины, и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени.[1][2] Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть чётным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём, когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф <math>G=(V,A)</math> содержит эйлеров цикл тогда и только тогда, когда он слабо связан или среди его компонент сильной связности только одна содержит ребра (а все остальные являются изолированными вершинами) и для каждой вершины графа её входящая степень <math>\mathrm{indeg}(\cdot)</math> равна её исходящей степени <math>\mathrm{outdeg}(\cdot)</math>, то есть в вершину входит столько же ребер, сколько из неё и выходит: <math>\mathrm{indeg}(v)=\mathrm{outdeg}(v)\quad \forall v\in V</math>.
Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф <math>G=(V,A)</math> содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф <math>G=(V,A)</math> содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда он слабо связен и существуют две вершины <math>p\in V</math> и <math>q\in V</math> (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами <math>\mathrm{indeg}(q)=\mathrm{outdeg}(q)+1</math> и <math>\mathrm{indeg}(p)=\mathrm{outdeg}(p)-1</math>, а все остальные вершины имеют одинаковые полустепени исхода и захода: <math>\mathrm{outdeg}(v)=\mathrm{indeg}(v)\quad \forall v\in V\setminus\{p,q\}</math>[3].
Поиск эйлерова пути в графе
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро.
Поиск эйлерова цикла в графе
Алгоритм Флёри
Шаблон:Mainref Алгоритм был предложен Флёри в 1883 году.
Пусть задан граф <math>G=(V,E)</math>. Начинаем с некоторой вершины <math>p\in V</math> и каждый раз вычеркиваем пройденное ребро. Не проходим по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин), т.е. необходимо проверять, является ли ребро мостом или нет.
Этот алгоритм неэффективен: время работы оригинального алгоритма O(|E|2). Если использовать более эффективный алгоритм для поиска мостов[4], то время выполнения можно снизить до <math>O(|E|(\log|E|)^3\log\log|E|)</math>, однако это всё равно медленнее, чем другие алгоритмы.
Алгоритм может быть распространен на ориентированные графы.
Алгоритм на основе циклов
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
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
- Теория графов и комбинаторика
- Графы. Циклы и разрезы (ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, Визуализаторы)
- Е. Гик. «Шахматы и математика» Конь-хамелеон
- Шаблон:MathWorld
- ↑ Шаблон:Cite web
- ↑ В. Алексеев, В. Таланов, Курс "Графы и алгоритмы", Лекция № 2 "Маршруты, связность, расстояния": Маршруты и связность в орграфах // Интуит.ру, 27.09.2006
- ↑ Кристофидес Н. Теория графов. Алгоритмический подход (глава 9.5) — М.: Мир, 1978.
- ↑ Шаблон:Статья
