Эйлеров цикл граф цепь(путь) кратко

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

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

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

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

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

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

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

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

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

Определение 3
Цепь, содержащая все ребра графа, называется эйлеровой.

Определение 4
Граф, обладающий эйлеровой цепью, называется квазиэйлеровым.

Теорема 5

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Флери

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

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

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

Алгоритм на основе циклов

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

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

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

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

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

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

Построение эйлерова цикла

Рассмотрим алгоритм построения эйлерова цикла в эйлеровом графе.
Алгоритм Флери.
Начиная с произвольной вершины, идем по ребрам графа, соблюдая следующие правила:
1. Удаляем ребра по мере их прохождения, и удаляем также изолированные вершины,
которые при этом образуются.
2. Идем по мосту только тогда, когда нет других возможностей.
Пример.

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

.Оценка числа эйлеровых графов

Лемма о числе вершин нечетной степени.

В любом графе число вершин нечетной степени четно. Доказательство. По теореме Эйлера сумма степеней вершин графа равна удвоенному количеству ребер, т. е. четному числу. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, значит, их четное число. Пусть N(p) – множество всех графов с p вершинами, а E(p) – множество всех эйлеровых графов с p вершинами

Теорема. Эйлеровых графов почти нет, т. е

Задача почтальона

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

при этом существуют

• . Задача почтальона для не ориентированных графов
• Задача почтальона для ориентированных графов
• Задача почтальона для смешаных графов

Смешаный граф – граф, в котором часть ребер ориентирована, а часть – не ориентирована. Для смешаных графов возможны случаи:

• 1) граф четный, симметричный;
• 2) граф четный, несимметричный;
• 3) граф нечетный, несимметричный.

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

Вау!! 😲 Ты еще не читал? Это зря!

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

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