Как найти эйлерову цепь на графе

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 10 августа 2021 года; проверки требуют 4 правки.

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

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

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

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

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

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

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

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

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

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

Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда он слабо связен и существуют две вершины и (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами и , а все остальные вершины имеют одинаковые полустепени исхода и захода: ^[3].

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

Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 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 году.

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

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

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

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

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

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

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.

Найти Эйлерову цепь в неориентированном псевдографе.

Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.

Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин

1) Выделим из G цикл m1. (так как степени вершин четны, то висячие вершины отсутствуют). Положим L=1, G¢=G.

2) Удаляем из G¢ ребра, принадлежащие выделенному циклу m1. Полученный псевдограф снова обозначаем как G¢. Если в G¢ отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G¢ цикл mL+1 и переходим к шагу 3.

3) Присваиваем L:=L+1 и переходим к шагу 2.

4) По построению выделенные циклы содержат все ребра по одному разу. Если L:=1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.

Пример.

Найдем Эйлерову цепь в неориентированном графе G, изображенном на рис. 10.

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

Рис. 10.

В рассматриваемом графе нечетные степени имеют вершины V3 и V1 (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф G¢:

Рис. 11.

Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы mI так, чтобы хотя бы один из них начинался или кончался на вершинах V3 или V1.

Пусть цикл m1 составят ребра, проходящие через следующие вершины: V3 V4 V7 V6 V1 V2 V3. Согласно алгоритму, удаляем из G¢ Все ребра, задействованные в цикле m1. Теперь граф G’ будет таким, как показано на рис. 12.

Составляем следующий цикл m2: V4 V5 V6 V2 V5 V7 V4. Граф G¢ после удаления ребер, составляющих цикл m2, изображен на рис. 13.

Очевидно, что последний цикл m3 будет состоять из V3 V5 V1|V3, где последнее ребро, соединяющее вершины V1 и V3 – фиктивно. После удаления ребер, составляющих цикл m3, в графе G¢ не останется ни одного ребра.

Теперь по общим вершинам склеиваем полученные циклы. Поскольку m1 и m2 имеют общую вершину V4, то, объединяя их, получим следующий цикл: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3. Теперь склеим получившийся цикл с циклом m3: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3 V5 V1|V3. Удаляя фиктивное ребро, получаем искомую Эйлерову цепь: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3 V5 V1.

Чтобы доказать эйлерову цепь, сперва сформулируем и докажем такую теорему:

Возьмем самый длинный путь

в

и рассмотрим одну из его конечных точек

. Эта вершина примыкает к предпоследней вершине пути. Так как у

степень не меньше двух, то должно существовать еще одно ребро, инцидентное ей.

Если другая конечная точка этого ребра не находится на пути, то мы могли бы использовать, чтобы построить более длинный путь, чем

. Это невозможно, поэтому другая конечная точка ребра должна быть вершиной

пути. Это создает цикл от

к

и обратно к

.

У этой теоремы много применений. Здесь мы используем ее для доказательства теоремы об эйлеровых схемах. В доказательстве мы будем использовать термин четный граф для обозначения графа, в котором степень каждой вершины четная.

Докажем еще следующую теорему:

Если в

есть эйлерова цепь, то эта цепь должна входить и выходить из каждой вершины. Такое возможно несколько раз, если добавлять

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

Докажем третью теорему — обратную импликацию индукцией по числу ребер. Базовый случай

ребер тривиально верен — это значит, что в графе есть только одна вершина и нет ребра.

Предположим, что утверждение справедливо для всех связных четных графов с e ребрами или меньше, и рассмотрим связный четный граф

с

ребром. Поскольку

связный и четный, у каждой вершины степень не менее двух, поэтому по Теореме у

есть цикл. Удалим ребра цикла из

.

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

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

Чтобы получить эйлерову схему всего графа, начнем прослеживать цикл от

до

. Далее проследим эйлерову схему, которая существует в правой компоненте графа, начинается и заканчивается в

.

После этого проследим цикл от

до

, от

до

. В точке

мы следуем эйлеровой схеме, которая существует на левой компоненте графа, начинается и заканчивается в точке

. В конце мы возвращаемся по циклу от

до

, и завершаем эйлерову схему всего графа. Значит, теорема доказана.

Мы предполагаем, что можем работать с небольшими случаями и использовать, чтобы строить более крупные случаи. Большая часть работы заключается в описании того, как использовать малые случаи для получения больших.

1. Эйлеровы цепи и циклы

Пусть
G
– псевдограф. Цепь (цикл) в G
называется эйлеровой
(эйлеровым), если
она (он) проходит по одному разу через
каждое ребро псевдографа G.

Для
того, чтобы связный псевдограф G
обладал эйлеровым циклом, необходимо
и достаточно, чтобы степени его вершин
были четными.

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

Пусть
G
– связный мультиграф, степени вершин
которого – четные числа.

1. Построить эйлеров цикл в графе. А л г о р и т м построения эйлерова цикла

Данные:
матрица инцидентности В(G)
мультиграфа G.

Результат:
последовательность ребер, образующих
эйлеров цикл.

1. Выбрать
   произвольную вершину v.

2. Выбрать
   произвольное ребро x,
   инцидентное v,
   и присвоить ему номер 1. (Назовем это
   ребро “пройденным”).

3. Каждое
   пройденное ребро вычеркивать и
   присваивать ему номер, на единицу
   больший номера предыдущего вычеркнутого
   ребра.

4. Находясь
   в вершине w,
   не выбирать ребра, соединяющего w
   с v,
   если только есть возможность другого
   выбора.

5. Находясь
   в вершине w,
   не выбирать ребра, которое является
   “перешейком” (при удалении которого
   граф, образованный незачеркнутыми
   ребрами, распадается на две компоненты
   связности, имеющие хотя бы по одному
   ребру).

6. После
   того, как в графе будут занумерованы
   все ребра, цикл 
   = [x_i1,
   x_i2,…,
   x_im],
   образованный
   ребрами с номерами от 1 до m,
   где m
   – число ребер в графе, есть эйлеров
   цикл.

Замечание.
Прежде чем строить эйлеров цикл, проверить
условие существования этого цикла.

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

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

1. Гамильтоновы цепи и циклы

Пусть G
– псевдограф.
Цепь (цикл) в G
называется
гамильтоновой
(гамильтоновым),
если она (он) проходит через каждую
вершину псевдографа G
ровно один раз. Простейшим достаточным
условием существования гамильтоновых
цепей и циклов в графе является его
полнота. Граф G
называется полным,
если каждая его вершина смежна со всеми
остальными вершинами. Необходимым
условием существования гамильтоновых
цепей и циклов в графе G
является связность данного графа.

Приведем некоторые
наиболее простые методы выделения
гамильтоновых цепей и циклов в графе G
=(V,X),
где V
= {v₁
,v₂
,…,v_n}.
Самым простым является метод перебора
всевозможных перестановок v_i1
,v_i2
,…,v_in
множества
V.
Для каждой из них проверяем, является
ли v_i1v_i2…v_in
маршрутом в
G.
Если является, то v_i1v_i2
…v_in
– гамильтонова
цепь в G,
в противном случае переходим к другой
перестановке. Тогда по окончании перебора
будут выделены все гамильтоновы цепи
в графе G.
Аналогично для выделения гамильтоновых
циклов перебираем всевозможные
перестановки v₁v_i1v_i2
…v_in-1
множества V,
для каждой из которых проверяем, является
ли v₁v_i1v_i2…v_in-1v₁
маршрутом
в G.
Если является, то v₁v_i1v_i2…v_in-1v₁
– гамильтонов цикл в
G,
в противном случае переходим к следующей
перестановке. Тогда по окончании перебора
будут выделены все гамильтоновы циклы
в графе G.
Очевидно, что при выделении гамильтоновых
цепей придется перебрать n!
перестановок, а при выделении всех
гамильтоновых циклов – (n-1)!
перестановок. При этом в случае полного
графа ни одна из перестановок не окажется
отброшенной, т.е. данный метод является
эффективным для графов, близких к полным.

Отметим, что
описанный метод не учитывает информации
об исследуемом графе G
и является как бы ориентированным на
самый “худший” случай, когда G
– полный граф.

Для
того, чтобы сократить число шагов в
предложенном методе, рассмотрим следующий
алгоритм. Предположим, что решение
имеет вид последовательности <v₁,
… v_n>. Идея метода состоит в
следующем: решение строится последовательно,
начиная с пустой последовательности
(длины 0). Далее, имея частичное решение
<v₁, … v_i>, ищем
такое допустимое значение v_i+1,
которое еще не было использовано,
добавляем его к пройденному частичному
решению и продолжаем процесс для нового
частичного решения <v₁, …
v_i+1>. В противном случае, если
такого значения v_i+1 не существует,
возвращаемся к предыдущему частичному
решению <v₁, … v_i-1>
и продолжаем процесс, пытаясь определить
новое, еще не использованное допустимое
значение v_k. Такие алгоритмы
носят название “алгоритмы с возвратом”
(англ.: backtracking).

2
1

1 5 3
12 14

4

123
125
143 145

1234 1235
1253 1254 1432
1435 1452 1453

14321
14352

12341
12354 12534

14325 14521
14532

12345
12541 12543 14523

123541
125341 143521
145321

Рис. 2

Процесс
поиска с возвращением удобно
проиллюстрировать в терминах обхода в
глубину в некотором дереве поиска,
которое строится следующим образом.
Каждая вершина дерева соответствует
некоторому частичному решению <v₁,…v_i>,
причем вершины, соответствующие
последовательностям вида <v₁,..
v_i, y>, и являются преемниками
вершины <v₁,… v_i>.
Корнем данного дерева является пустая
последовательность. В случае построения
гамильтонова цикла в качестве корня
может выступать любая вершина.

При обходе дерева
в глубину вершины дерева посещаются в
таком порядке: сначала посещаем корень
дерева v₁, а затем (если v₁
– не висячая вершина) для каждого
преемника v_i корня v₁
рекурсивно обращаемся к процедуре
обхода в глубину для того, чтобы обойти
все поддеревья с корнями v_i в
порядке, в котором упорядочены вершины
v_i как преемники корня v₁.

Пример.

На рис.2 показаны
граф и дерево, иллюстрирующее процесс
нахождения всех гамильтоновых циклов
с помощью алгоритма с возвратом.

Гамильтоновы циклы
– 123541, 125341, 143521, 145321.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Эйлеров путь и цикл

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

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

Алгоритм поиска Эйлеров цикла

Сервис использует алгоритм поиска Эйлеров цикла на основе циклов.

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

Кроме того, перед поиском цикла проверяется его существование, для этого происходит поиск степени вершин.

Более подробно вы можете узнать об этом алгоритме
в Википедии.

Реализацию алгоритма на языке C++ вы можете найти в нашем репозитории на GitHub: Реализация поиска Эйлерового цикла в Graphoffline.

Алгоритм поиска Эйлервой цепи

Для поиска Эйлеров пути мы добавляем псевдо ребро соединяющие начальную и конечную вершину Эйлерова пути.

Начальная и конечная вершина для неориентированного графа будет иметь нечётные степени.

Для ориентированного графа начальная вершина имеет полустепень исхода на единицу больше полустепени захода. Для конечной вершины полустепень исхода на единицу меньше полустепени захода.

Как использовать

1. Создайте граф.
2. Выберите пункт меню Алгоритмы -> “Найти Эйлеров цикл” для поиска Эйлеров цикл.

1. Выберите пункт меню Алгоритмы -> “Найти Эйлерову цепь” для поиска Эйлеровой цепи.