Эйлеров граф как определить

3.12. Эйлеровы графы

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

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

Пример 1.Рассмотрим граф: ,,,,. Циклэйлеров. Следовательно,— эйлеров граф.

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

Доказательство.Так как степени вершин графачетные, то. Имеем:

.

Так что , и, значит,. Следовательно, согласно основной теореме о деревьях графне может быть деревом, а, значит, на графе имеется хотя бы один цикл.■

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

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

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

Пусть — эйлеров цикл на графеи— произвольная вершина графа.

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

а) вершина не совпадает с началом и концом цикла;

б) вершина совпадает с началом и концом цикла.

Двигаясь по эйлерову циклу, будем подсчитывать число ребер, инцидентных вершине . В первом случае это будут ребра, совпадающие с теми членами последовательности , которые имеют номера , , , ,…, , . Общее число этих членов и есть степень вершины, т.е.. Во втором случае ребра, инцидентные вершине, совпадают с членами последовательности , имеющими номера , ,,…, ,, . Следовательно,. Как в первом, так и во втором случае степень вершинычетна.

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

Базис индукции.Пусть, т.е. граф имеет одно ребро (обозначим его). Концы этого ребра имеют четную степень только если это ребро – петля и совпадающие концы этого ребра – единственная вершина графа (обозначим ее). Следовательно, на графе имеется эйлеров цикл:, так что граф – эйлеров.

Индуктивный переход.Предположим, что утверждение верно для любого связного графа с числом ребер меньшим либо равным. Покажем, что оно остается в силе для графа, число ребер которого равно. Согласно лемме на графеимеется цикл. Обозначим его. Если этот цикл проходит через все ребра графа, то он и есть искомый эйлеров цикл и индуктивный переход доказан. В противном случае рассмотрим граф, полученный изудалением ребер этого цикла (обозначим его). Каждая компонента связности графа— либо изолированная вершина, либо связный ненулевой граф с вершинами четных степеней и числом ребер меньшим, либо равным. Значит, по предположению индукции на каждой ненулевой компоненте связности существует эйлеров цикл. Обозначим эти циклы. Поскольку исходный граф связен, то циклимеет хотя бы по одной общей вершине с компонентами связности графа. Выберем на каждой ненулевой компоненте связности графа по одной вершине, общей с циклом, и обозначим эти вершины(). Эйлеров цикл на графепостроим следующим образом: отправимся по циклуиз его начала и будем двигаться по нему до тех пор, пока не встретим вершину из множества, пусть это будет вершина; прервем движение по циклуи, начав с вершины, обойдем эйлеров цикл; после чего продолжим движение по циклу, до тех пор, пока не встретим вершину из множества, пусть это будет вершина; опять прервем движение по циклуи пройдем по эйлерову циклуи так далее, до тех пор, пока не обойдем всего цикла. Склеив соответствующие фрагменты циклови, получим искомый эйлеров цикл. ■

Пример 2.Свое название эйлеровы графы получили в честь Л. Эйлера, который первым рассмотрел такие графы в 1736 году в своей знаменитой работе о кенигсбергских мостах. Задача эта состояла в следующем. На реке Прегель в Кенигсберге было два острова, соединенных между собой и с берегами семью мостами, как показано на рисунке 1. Спрашивается, можно ли, начиная с некоторого места суши, обойти все мосты по одному разу и вернуться назад?

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

Эйлеровость графов

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. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Проверить, является ли неориентированный graph эйлеровым

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

1. Эйлерова тропа (или эйлерова тропа, или эйлерова прогулка)

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

1. Ровно ноль или две вершины имеют нечетную степень, и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Следующий graph не является эйлеровым, поскольку четыре вершины имеют нечетную степень вхождения (0, 2, 3, 5):

2. Эйлерова схема (или эйлеров цикл, или эйлеров цикл)

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

1. Каждая вершина имеет четную степень и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Например, следующий graph имеет эйлеров цикл, так как каждая вершина имеет четную степень:

3. Полуэйлерова

Граф, который имеет эйлеров след, но не имеет эйлеровой цепи, называется полуэйлеровым. Неориентированный graph является полуэйлеровым тогда и только тогда, когда

1. ровно две вершины имеют нечетную степень и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Следующий graph является полуэйлеровым, поскольку существует ровно две вершины с нечетной степенью вхождения (0, 1):

Следующая реализация на C++, Java и Python проверяет, является ли данный graph эйлеровым и содержит ли он эйлеров цикл:

10. Эйлеровы графы. Условия существования цепи и цикла. Гамильтоновы цепи и циклы.

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

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

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

Условия существования цепи и цикла.

Лемма 1. Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.

Теорема Эйлера 2. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четная степень.

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

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

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

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

Любой простой полный граф с нечетным количеством вершин является эйлеровым.

Любой циклический граф является эйлеровым.

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

Гамильтонов цикл — цикл, проходящий ровно один раз через каждую вершину графа G.

Тогда граф G называется гамильтоновым графом.

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

Теорема 4 (Дирарк, 1952).

Если в простом графе G с n>=3 вершинами степень любой вершины v scr37 , то граф G является гамильтоновым.