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

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

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

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

Данный граф является эйлеровым, так как он имеет эйлеров цикл (x₂, x₅, x₄, x₁, x₂, x₃, x₄, x₂).

Теорема 1. Эйлеров граф связный, и все его вершины четны.

Доказательство.

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

Теорема 2. Если граф G(X,T) связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 3. Если граф G(X,T) обладает эйлеровым путем с концами А и В, то граф G(X,T) связный и А и В его единственные нечетные вершины.

Доказательство.

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

Теорема 4. Если граф G(X,T) связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.

Теорема 5. Если граф G(X,T) связный, то можно построить цикличный маршрут, содержащий все ребра в точности 2 раза, по одному в каждом направлении.

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

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

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

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

Задачи с эйлеровыми графами часто встречаются в книгах по занимательной математике — например, можно ли нарисовать какую-нибудь диаграмму, не отрывая карандаша от бумаги и не проходя никакую линию дважды. Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о Кенигсбергских мостах, в которой нужно было узнать, имеет ли граф , изображенный на рисунке, эйлерову цепь (не имеет!).

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

Теорема 4.1. Если граф обладает эйлеровым циклом, то он является связным, а все его вершины — четными.

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

Верно и обратное утверждение.

Теорема 4.2. Если граф связный и все его вершины четные, то он обладает эйлеровым циклом.

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

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

Все вершины графа имеют четные степени, поэтому если есть » выход » из alt=»v_» />, то должен быть и «вход» в alt=»v_» />, так же как и для любой другой вершины. И если есть «вход» в вершину, то должен быть и » выход «.

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

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

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

Так как , тоже четно. Начнем новый путь из . Этот путь кончится в обозначен прямыми линиями со стрелками. Объединим теперь оба цикла : из пройдем по пути к и, вернувшись в .

Если снова найдутся ребра, которые не вошли в путь , то найдем новые циклы. Число ребер и вершин конечно, процесс закончится.

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

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

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

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 является гамильтоновым.