Что такое эйлеров цикл
Эйлеров цикл
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
Содержание
Существование эйлерова цикла и эйлерова пути
Эйлеров цикл/путь существуют только в связных графах или в графах, которые после удаления всех одиночных вершин превратятся в связные.
В неориентированном графе
Кроме того, согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени. [1] [2] Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть четным. А значит Эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит.
Поиск эйлерова пути в графе
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
Достаточно вызвать эту процедуру из любой неодиночной вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.
Для поиска цикла на шаге 1 используем поиск в глубину.
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Примечания
См. также
Ссылки
Полезное
Смотреть что такое «Эйлеров цикл» в других словарях:
эйлеров цикл — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN euler cycle … Справочник технического переводчика
Цикл Эйлера — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Эйлеров путь — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Эйлеров интеграл — Существует множество математических и физических объектов, названных в честь Леонарда Эйлера: Содержание 1 Теоремы 2 Лемма 3 Уравнения 4 Тождества 5 … Википедия
Цикл Гамильтона — Граф додекаэдра с выделенным циклом Гамильтона Гамильтонов граф в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл. Гамильтонов путь (или гамильтонова цепь) путь (цепь), содержащий каждую вершину графа ровно один раз.… … Википедия
Простой цикл — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Эйлеровы графы — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Эйлеров путь
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
Содержание
Существование эйлерова цикла и эйлерова пути
Разумеется, эйлеров цикл/путь существуют только в связных графах или в графах, которые после удаления всех одиночных вершин превратятся в связные.
В неориентированном графе
Кроме того, согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда в графе отсутствуют вершины нечётной степени. Эйлеров путь существует тогда и только тогда, когда число вершин нечётной степени не превосходит двух.
Теорема: Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. [1] [2]
В ориентированном графе
Связный ориентированный граф содержит эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из нее и выходит.
Поиск эйлерова пути в графе
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществуещее ребро.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
Достаточно вызвать эту процедуру из любой неодиночной вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.
Для поиска цикла на шаге 1 используем поиск в глубину.
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Пример реализации на C++
Примечания
См. также
Ссылки
Полезное
Смотреть что такое «Эйлеров путь» в других словарях:
Эйлеров цикл — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует … Википедия
Эйлеров интеграл — Существует множество математических и физических объектов, названных в честь Леонарда Эйлера: Содержание 1 Теоремы 2 Лемма 3 Уравнения 4 Тождества 5 … Википедия
Путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Простой путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Эйлеровы графы — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Цикл Эйлера — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Список объектов, названных в честь Леонарда Эйлера — Существует множество математических и физических объектов, названных в честь Леонарда Эйлера: Содержание 1 Теоремы 2 Лемма 3 Уравнения 4 … Википедия
Интеграл Эйлера — Существует множество математических и физических объектов, названных в честь Леонарда Эйлера: Содержание 1 Теоремы 2 Лемма 3 Уравнения 4 Тождества 5 … Википедия
Эйлеровы интегралы — Существует множество математических и физических объектов, названных в честь Леонарда Эйлера: Содержание 1 Теоремы 2 Лемма 3 Уравнения 4 Тождества 5 … Википедия
Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
Эйлеров цикл
Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.
Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.
Для простоты в обоих случаях будем считать, что граф неориентированный.
Граф на пяти вершинах и один из его эйлеровых циклов: CDCBBADEBC
Также существует понятие гамильтонова пути и цикла — они посещают все вершины по разу, а не рёбра. Нахождение гамильтонова цикла (задача коммивояжера, англ. travelling salesman problem) — одна из самых известных NP-полных задач, в то время как нахождение эйлерова цика решается за линейное время, и мы сейчас покажем, как.
Нахождение эйлерова цикла
Теорема. Эйлеров цикл существует тогда и только тогда, когда граф связный и степени всех вершин чётны.
Доказательство. Необходимость показывается так: можно просто взять эйлеров цикл и ориентировать все его ребра в порядке обхода. Тогда из каждой вершины будет выходить столько же рёбер, сколько входить, а значит степень у всех вершин исходного неориентированного графа была четной.
Достаточность докажем конструктивно — предъявим алгоритм нахождения цикла:
Значит, если условия на связность и четность степеней выполняются, то выведенная последовательность вершин действительно будет эйлеровым циклом, причём и в случае ориентированного графа тоже.
Как удалять ребра
Также можно использовать более общий подход, который часто применяется в задачах, где ребра как-то изменяются. Создадим отдельный массив с мета-информацией о ребрах и будем хранить в списках смежности не номера вершин, а номера рёбер:
Тогда во время обхода можно поддерживать эту информацию вместо какой-то сложной модификации структур:
Во всех вариантах реализации нужно быть чуть аккуратнее в случае, когда в графе есть петли и кратные ребра.
Эйлеров путь
Поговорим теперь про эйлеровы пути. Может, всё-таки можно что-нибудь сделать, даже если степени не всех вершин чётные?
Заметим, что, так как каждое ребро меняет четность степеней ровно двух вершин, и в пустом графе все степени изначально нулевые, то число вершин с нечетными степенями будет четным.
Если нечетных вершин ровно две, то можно сделать следующее: соединить их ребром, построить эйлеров цикл (ведь теперь степени всех вершин четные), а затем удалить это ребро из цикла. Если правильно сдвинуть этот цикл, мы получили эйлеров путь.
Альтернативно, можно просто запустить обход из одной из нечетных вершин и получить такой же результат.
Если нечетных вершин больше двух, то мы уже построить эйлеров путь не сможем, потому что любой эйлеров путь входит или покидает каждую вершину четное число раз, кроме, возможно двух своих концов.
Следствие. Эйлеров путь существует тогда и только тогда, когда граф связен и количество вершин с нечётными степенями не превосходит 2.
Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.
Эйлеровость графов
Содержание
Основные определения [ править ]
| Определение: |
| Эйлеровым путем (англ. Eulerian path) в графе называется путь, который проходит по каждому ребру, причем ровно один раз. |
| Определение: |
| Эйлеров обход (англ. Eulerian circuit) — обход графа, посещающий эйлеров путь. |
| Определение: |
| Эйлеров цикл (англ. Eulerian cycle) — замкнутый эйлеров путь. |
| Определение: |
| Граф называется эйлеровым (англ. Eulerian graph), если он содержит эйлеров цикл. Граф называется полуэйлеровым, если он содержит эйлеров путь, но не содержит эйлеров цикл. |
Критерий эйлеровости [ править ]
1. Все вершины имели четную степень.
2. Все компоненты связности кроме, может быть одной, не содержали ребер.
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
1. Все вершины имеют четную степень.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
База индукции: [math]n = 0[/math] цикл существует.
Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.
Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны.
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Ориентированный граф [ править ]
1. Входная степень любой вершины равна ее выходной степени.
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.