Эйлеров цикл

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

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

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

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).

Существование эйлерова цикла и эйлерова пути[править | править вики-текст]

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

В неориентированном графе[править | править вики-текст]

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

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

В ориентированном графе[править | править вики-текст]

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

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

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

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

Поиск эйлерова цикла в графе[править | править вики-текст]

Алгоритм Флёри[4][править | править вики-текст]

Это хоть и элегантный, но неэффективный алгоритм, который был предложен Флёри в 1883 году.

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

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

Алгоритм на основе циклов[править | править вики-текст]

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

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

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

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

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

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

Примечания[править | править вики-текст]

  1. Эйлеровы пути
  2. В. Алексеев, В. Таланов, Курс "Графы и алгоритмы", Лекция № 2 "Маршруты, связность, расстояния": Маршруты и связность в орграфах // Интуит.ру, 27.09.2006
  3. Кристофидес Н. Теория графов. Алгоритмический подход (глава 9.5) — М.: Мир, 1978.
  4. Fleury, M. (1883), "«Deux problèmes de Géométrie de situation»", Journal de mathématiques élémentaires, 2nd ser. Т. 2: 257–261, <http://books.google.com/books?id=l-03AAAAMAAJ&pg=PA257> .

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]