Эйлерова цепь в графе как найти – Сайт, где вы сможете решить свои вопросы

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

Если

— граф, в котором у каждой вершины степень не менее двух, то

содержит цикл

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

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

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

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

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

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

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

и обратно к

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

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

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

Если в

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

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

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

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

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

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

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

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

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

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

eyJpZCI6IjEyY2I4NmI4MGE1OGJiNmNmMWIxNWIyNTY4Zjg1MmMwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2a3a6e4e2d9ed36315103eda0e49211a58e44e269d413980396ee6feacceb913

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

до

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

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

до

, от

до

. В точке

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

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

до

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф $G=(V,A)$ содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф $G=(V,A)$ содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда он слабо связен и существуют две вершины $pin V$ и $qin V$ (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами ${mathrm {indeg}}(q)={mathrm {outdeg}}(q)+1$ и ${mathrm {indeg}}(p)={mathrm {outdeg}}(p)-1$ , а все остальные вершины имеют одинаковые полустепени исхода и захода: ${mathrm {outdeg}}(v)={mathrm {indeg}}(v)quad forall vin Vsetminus {p,q}$ ^[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 году.

Пусть задан граф $G=(V,E)$ . Начинаем с некоторой вершины $pin 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(|E|), то есть линейная относительно количества рёбер в данном графе.

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

↑ Эйлеровы пути. Дата обращения: 26 ноября 2008. Архивировано из оригинала 5 января 2009 года.
↑ В. Алексеев, В. Таланов, Курс “Графы и алгоритмы”, Лекция № 2 “Маршруты, связность, расстояния”: Маршруты и связность в орграфах // Интуит.ру, 27.09.2006
↑ Кристофидес Н. Теория графов. Алгоритмический подход (глава 9.5) — М.: Мир, 1978.
↑ Mikkel Thorup. Near-optimal fully[sic]-dynamic graph connectivity // Proceeding STOC ’00 Proceedings of the thirty-second annual ACM symposium on Theory of computing. — Portland: Association for Computing Machinery, 2000. — 21–23 5. — С. 343–350. — doi:10.1145/335305.335345.

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

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

Ссылки[править | править код]

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

Источник

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

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

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

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

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

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

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

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

Выбрать
произвольную вершину v.
Выбрать
произвольное ребро x,
инцидентное v,
и присвоить ему номер 1. (Назовем это
ребро “пройденным”).
Каждое
пройденное ребро вычеркивать и
присваивать ему номер, на единицу
больший номера предыдущего вычеркнутого
ребра.
Находясь
в вершине w,
не выбирать ребра, соединяющего w
с v,
если только есть возможность другого
выбора.
Находясь
в вершине w,
не выбирать ребра, которое является
“перешейком” (при удалении которого
граф, образованный незачеркнутыми
ребрами, распадается на две компоненты
связности, имеющие хотя бы по одному
ребру).
После
того, как в графе будут занумерованы
все ребра, цикл 
= [x_i₁,
x_i₂,…,
x_im],
образованный
ребрами с номерами от 1 до m,
где m
– число ребер в графе, есть эйлеров
цикл.

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

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

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

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

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

Приведем некоторые
наиболее простые методы выделения
гамильтоновых цепей и циклов в графе G
=(V,X),
где V
= {v₁
,v₂
,…,v_n}.
Самым простым является метод перебора
всевозможных перестановок v_i₁
,v_i₂
,…,v_in множестваV.
Для каждой из них проверяем, является
ли v_i₁v_i₂…v_in
маршрутом в G.
Если является, то v_i₁v_i₂
…v_in– гамильтонова
цепь вG,
в противном случае переходим к другой
перестановке. Тогда по окончании перебора
будут выделены все гамильтоновы цепи
в графе G.
Аналогично для выделения гамильтоновых
циклов перебираем всевозможные
перестановки v₁v_i₁v_i₂
…v_in_-1
множества V,
для каждой из которых проверяем, является
ли v₁v_i₁v_i₂…v_in_-1v₁маршрутом
в G.
Если является, то v₁v_i₁v_i₂…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

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.

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

Источник

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

// Класс для хранения ребра Graph

class Edge

{

int source, dest;

public Edge(int source, int dest)

{

this.source = source;

this.dest = dest;

}

// Класс для представления graphического объекта

class Graph

{

// Список списков для представления списка смежности

List<List<Integer>> adjList;

// Конструктор

Graph(List<Edge> edges, int n)

{

adjList = new ArrayList<>();

for (int i = 0; i < n; i++) {

adjList.add(new ArrayList<>());

}

// добавляем ребра в неориентированный graph

for (Edge edge: edges)

{

adjList.get(edge.source).add(edge.dest);

adjList.get(edge.dest).add(edge.source);

}

class Main

{

// Вспомогательная функция для обхода DFS на Graphе

public static void DFS(Graph graph, int v, boolean[] discovered)

{

// помечаем текущий узел как обнаруженный

discovered[v] = true;

// делаем для каждого ребра (v, u)

for (int u: graph.adjList.get(v))

{

// если `u` еще не обнаружен

if (!discovered[u]) {

DFS(graph, u, discovered);

}

// Функция для проверки, все ли вершины с ненулевой степенью в Graph

// принадлежат одному связанному компоненту

public static boolean isConnected(Graph graph, int n)

{

// чтобы отслеживать, посещена ли вершина или нет

boolean[] visited = new boolean[n];

// запускаем поиск в глубину с первой вершины с ненулевой степенью

for (int i = 0; i < n; i++)

{

if (graph.adjList.get(i).size() > 0)

{

DFS(graph, i, visited);

break;

}

// если один вызов DFS не может посетить все вершины с ненулевой степенью,

// graph содержит более одной компоненты связности

for (int i = 0; i < n; i++)

{

if (!visited[i] && graph.adjList.get(i).size() > 0) {

return false;

}

return true;

}

// Вспомогательная функция для возврата общего количества вершин в Graph

// с нечетной степенью

public static int countOddVertices(Graph graph)

{

int count = 0;

for (List<Integer> list: graph.adjList)

{

if ((list.size() & 1) == 1) {

count++;

}

return count;

}

public static void main(String[] args)

{

// Список ребер Graph согласно приведенной выше диаграмме

List<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(0, 3),

new Edge(1, 2), new Edge(1, 3), new Edge(1, 4),

new Edge(2, 3), new Edge(3, 4));

// общее количество узлов в Graph (от 0 до 4)

int n = 5;

// создаем неориентированный graph из заданных ребер

Graph graph = new Graph(edges, n);

// проверяем, все ли вершины с ненулевой степенью принадлежат

// одиночный связный компонент

boolean is_connected = isConnected(graph, n);

// находим общее количество вершин с нечетной степенью

int odd = countOddVertices(graph);

// Эйлеров путь существует, если все вершины не нулевой степени соединены,

// и ноль или две вершины имеют нечетную степень

if (is_connected && (odd == 0 || odd == 2))

{

System.out.println(“The graph has an Eulerian path”);

// Связный graph имеет эйлеров цикл, если каждая вершина имеет

// четная степень

if (odd == 0) {

System.out.println(“The graph has an Eulerian cycle”);

}

// В Graph есть эйлеров путь, но нет эйлерова цикла

else {

System.out.println(“The Graph is Semi–Eulerian”);

}

else {

System.out.println(“The Graph is not Eulerian”);

}

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

Алгоритм Флёри[править | править код]

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

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

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

Ссылки[править | править код]

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

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

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

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

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

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

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

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

Вам также может понравиться

Common language runtime debugging services как исправить

Как составить буклет рекомендации

Как найти бесплатную музыку для айфона

Добавить комментарий Отменить ответ