Эйлеровость графов
2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
1. Все вершины имеют четную степень.
2. Все компоненты связности, кроме, может быть, одной, не содержат ребер.
Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин [math]n[/math] .
База индукции: [math]n = 0[/math] цикл существует.
Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.
Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны.
Пусть [math]v_1[/math] и [math]v_2[/math] — вершины графа. Поскольку граф связный, то существует путь из [math]v_1[/math] в [math]v_2[/math] . Степень [math]v_2[/math] — чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из [math]v_2[/math] . Так как граф конечный, то путь, в конце концов, должен вернуться в [math]v_1[/math] , следовательно мы получим замкнутый путь (цикл). Назовем этот цикл [math]C_1[/math] . Будем продолжать строить [math]C_1[/math] через [math]v_1[/math] таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины [math]v_1[/math] , то есть [math]C_1[/math] будет покрывать все ребра, инцидентные [math]v_1[/math] . Если [math]C_1[/math] является эйлеровым циклом для [math]G[/math] , тогда доказательство закончено. Если нет, то пусть [math]G'[/math] — подграф графа [math]G[/math] , полученный удалением всех рёбер, принадлежащих [math]C_1[/math] . Поскольку [math]C_1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень. А так как [math]C_1[/math] покрывает все ребра, инцидентные [math]v_1[/math] , то граф [math]G'[/math] будет состоять из нескольких компонент связности.
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Ориентированный граф
1. Входная степень любой вершины равна ее выходной степени.
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых [math]\operatorname
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
§ 6. Эйлеров граф и условия его существования
Задача о кенигсбергских мостах. Постановка и решение Эйлером этой задачи знаменует начало разработки теории графов. Расположение мостов приведено на рис. 3.15, а.
Рис. 3.15. Расположение мостов: а — схема мостов, б — граф F, соответствующий схеме мостов
Требуется пройти каждый мост по одному разу и вернуться в исходную часть города. Можно построить граф задачи, в котором каждой части города соответствует вершина, а каждому мосту ребро, инцидентное вершинам, относящимся к соединяемым им частям (рис. 3.15, б).
Обходу мостов соответствует последовательность рёбер графа F, в которой два соседних ребра имеют общую вершину, т.е. маршрут. Так как в конце обхода нужно вернуться в исходную часть города и на каждом мосту побывать по одному разу, то этот маршрут является циклом, содержащим все рёбра графа. Такие циклы называются эйлеровыми, а графы, имеющие эйлеровы циклы, — эйлеровыми графами.
Эйлеров цикл можно считать следом карандаша, вычерчивающего этот граф, не отрываясь от бумаги, причём процесс изображения графа начинается и кончается в одной и той же точке.
Примером эйлерова графа является фигура, которая называется сабли Магомета и имеет арабское происхождение (рис. 3.16).
Рис. 3.16.
Условия, при которых псевдограф эйлеров
Теорема 3.3 (Эйлера). Конечный неориентированный псевдограф F эйлеров, тогда и только тогда, когда он связный и степени всех его вершин чётны.
Необходимость. Пусть конечный неориентированный граф F эйлеров.
По определению, эйлеров граф имеет цикл, содержащий все рёбра этого графа. Это значит, что в эйлеровом графе всегда найдётся маршрут, соединяющий любые две его вершины. Следовательно, эйлеров граф связен.
Рассмотрим какую-нибудь произвольную вершину vi графа F, отличную от начала эйлерова цикла. Каждый раз, когда эйлеров цикл приходит в эту вершину по одному ребру, он должен выйти из неё по другому ребру; поэтому каждый такой проход даёт вклад 2 в степень вершины. Если вершину vi прошли в общей сложности k раз, то степень этой вершины равна 2k, т.е. чётна.
Рассмотрим теперь вершину v0, которая является началом (и концом) эйлерова цикла. Каждый выход из этой вершины по одному ребру плюс возврат в неё по другому ребру даёт вклад 2 в степень этой вершины. Если из начальной вершины выходили m раз, то и возвращались в неё m раз, следовательно, степень этой вершины равна 2m (тоже чётна).
Достаточность. Пусть граф F связный и степени всех его вершин чётны.
Начнём построение эйлерова цикла с произвольной вершины v0 графа F. Каждый раз, когда мы добавляем к маршруту новое ребро и приходим в новую вершину vi (viv0), число “свободных” (непройденных) рёбер в этой вершине уменьшается на единицу. Так как до этого оно было чётным, то теперь становится нечётным, а значит, не может оказаться нулём; поэтому закончиться в вершине vi эйлеров цикл не может. Напротив, каждый выход из исходной вершины v0 плюс возврат в неё уменьшает число “свободных” (непройденных) рёбер на 2 и, в конце концов, станет нулём, а значит, процесс построения цикла может закончиться только в вершине v0.
Совсем не обязательно, что построенный таким образом цикл проходит через все рёбра графа F. Параллельно дальнейшему изложению будем рассматривать простой пример, который облегчит понимание последней части доказательства.
Рис. 3.17. Эйлеров граф F.
Предположим, что, выйдя из вершины v0 (рис. 3.17) и пройдя по маршруту 1-2-3-4, мы вернулись в v0. Принадлежащие построенному циклу рёбра порождают связную часть C графа F, в которой степени всех вершин чётны (на рис. 3.17 рёбра графа C проведены сплошной линией). Значит, чётными будут и степени вершин графа F1=F\C (на рис. 3.17 рёбра графа F1 обозначены пунктирной линией).
Так как F, по условию, связный граф, то в C найдётся хотя бы одна вершина v*, инцидентная также рёбрам из F1. Начиная с этой вершины, можно, как и ранее, построить цикл C* в F1, кончающийся также в v* (на рис. 3.17 цикл C* — 5-6-7).
Эта вершина, кроме того, разбивает цикл C на 2 участка: C1 с началом в v0 и концом в v* (на рис. 3.17 участок C1 — 1-2-3) и C2 с началом в v* и концом в v0 (на рис. 3.17 участок C2 — 4). Тогда C1 C* C2 также является циклом, начинающимся и кончающимся в вершине v0, но имеющим большее число рёбер (на рис. 3.17 цикл 1-2-3-5-6-7-4 — включает все рёбра графа F).
В общем случае и этот цикл не обязательно проходит через все рёбра графа F. Тогда процесс расширения цикла аналогичным образом повторяют. Каждый раз число рёбер в цикле увеличивается не менее чем на два, следовательно, в конце концов, эйлеров цикл будет построен.
В графе задачи о кенигсбергских мостах все вершины имеют нечётную степень, значит, решение этой задачи невозможно.
Флёри дал очень простой алгоритм построения эйлерова цикла в неор. графе (если такой цикл существует). Этот алгоритм можно легко распространить и на орграфы. Начать с некоторой вершины p и каждый раз вычеркивать пройденное ребро. Не проходить по ребру, если удаление этого ребра приводит к разбиению графа на 2 связные компоненты (не считая изолир-х вершин).
Эйлеровой называют цепь, включающую все рёбра данного конечного неориентированного графа G, но имеющую различные начало v’ и конец v’’.
Необходимыми и достаточными условиями существования в конечном неориентированном псевдографе эйлеровой цепи являются его связность и чётность степеней всех его вершин, кроме начальной v’ и конечной v’’. Последние две вершины должны иметь нечётные степени.
Эйлеров граф как определить
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
Содержание
Существование эйлерова цикла и эйлерова пути
Разумеется, эйлеров цикл/путь существуют только в связных графах или в графах, которые после удаления всех одиночных вершин превратятся в связные.
В неориентированном графе
Кроме того, согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда в графе отсутствуют вершины нечётной степени. Эйлеров путь существует тогда и только тогда, когда число вершин нечётной степени не превосходит двух.
Теорема: Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени. [1] [2]
В ориентированном графе
Связный ориентированный граф содержит эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из нее и выходит.
Поиск эйлерова пути в графе
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществуещее ребро.
Поиск эйлерова цикла в графе
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
Достаточно вызвать эту процедуру из любой неодиночной вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.
Для поиска цикла на шаге 1 используем поиск в глубину.
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Пример реализации на C++
Примечания
- ↑Эйлеровы пути
- ↑Маршруты и связность в орграфах
См. также
Ссылки
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое «Эйлеровы графы» в других словарях:
Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
Граф (теория графов) — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Неориентированный граф — с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для разных областей… … Википедия
Орграф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Простой цикл — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Цикл Эйлера — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Эйлеров путь — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Эйлеров цикл — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует … Википедия
Гамильтонов граф — Граф додекаэдра с выделенным циклом Гамильтона … Википедия
Эйлеровость графов
2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
1. Все вершины имеют четную степень.
2. Все компоненты связности, кроме, может быть, одной, не содержат ребер.
Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин [math]n[/math] .
База индукции: [math]n = 0[/math] цикл существует.
Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.
Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны.
Пусть [math]v_1[/math] и [math]v_2[/math] — вершины графа. Поскольку граф связный, то существует путь из [math]v_1[/math] в [math]v_2[/math] . Степень [math]v_2[/math] — чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из [math]v_2[/math] . Так как граф конечный, то путь, в конце концов, должен вернуться в [math]v_1[/math] , следовательно мы получим замкнутый путь (цикл). Назовем этот цикл [math]C_1[/math] . Будем продолжать строить [math]C_1[/math] через [math]v_1[/math] таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины [math]v_1[/math] , то есть [math]C_1[/math] будет покрывать все ребра, инцидентные [math]v_1[/math] . Если [math]C_1[/math] является эйлеровым циклом для [math]G[/math] , тогда доказательство закончено. Если нет, то пусть [math]G'[/math] — подграф графа [math]G[/math] , полученный удалением всех рёбер, принадлежащих [math]C_1[/math] . Поскольку [math]C_1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень. А так как [math]C_1[/math] покрывает все ребра, инцидентные [math]v_1[/math] , то граф [math]G'[/math] будет состоять из нескольких компонент связности.
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Ориентированный граф [ править ]
1. Входная степень любой вершины равна ее выходной степени.
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых [math]\operatorname ^+ — \operatorname ^- = 1[/math] , а для другой [math]\operatorname ^+ — \operatorname ^- = -1[/math] .
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
Эйлеровы графы
Данный граф является эйлеровым, так как он имеет эйлеров цикл (x2, x5, x4, x1, x2, x3, x4, x2).
Теорема 1. Эйлеров граф связный, и все его вершины четны.
Доказательство.
Связность следует из определения эйлерового графа. Эйлеров цикл содержит каждое ребро и притом только один раз. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: количество входов в вершину и количество выходов из вершины.
Теорема 2. Если граф G(X,T) связный и все его вершины четны, то он обладает эйлеровым циклом.
Теорема 3. Если граф G(X,T) обладает эйлеровым путем с концами А и В, то граф G(X,T) связный и А и В его единственные нечетные вершины.
Доказательство.
Если путь начинается в А и кончается в В, то А и В нечетные вершины, даже если путь неоднократно проходил через них. В любую другую вершину путь должен привести и вывести из нее, т.е. остальные вершины четные.
Теорема 4. Если граф G(X,T) связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.
Теорема 5. Если граф G(X,T) связный, то можно построить цикличный маршрут, содержащий все ребра в точности 2 раза, по одному в каждом направлении.
Как найти эйлеров путь в графе
Для того чтобы найти эйлеров путь в графе, необходимо проверить, является ли граф эйлеровым. Эйлеров граф — это граф, в котором существует цикл, который проходит через каждое ребро ровно один раз. Эйлеров путь — это путь, который проходит через каждое ребро ровно один раз.
Чтобы определить, является ли граф эйлеровым, можно использовать следующие критерии:
Каждая вершина имеет четную степень (количество инцидентных ребер).
Существует ровно две вершины с нечетной степенью.
Если хотя бы одно из этих условий не выполняется, то граф не является эйлеровым.
Если граф является эйлеровым, то эйлеров путь можно найти, используя алгоритм Флери. Алгоритм Флери начинается с выбора произвольной вершины и последующего прохождения по ребрам графа, пока все ребра не будут пройдены. При этом при прохождении необходимо избегать повторного прохождения по уже пройденным ребрам. Если в результате применения алгоритма Флери получится путь, который проходит через каждое ребро ровно один раз, то это будет эйлеров путь.