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

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 эйлеровым и содержит ли он эйлеров цикл:

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

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

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

Рисунок 1.13 Рисунок 1.14

Решение задачи Эйлера о семи кёнигсбергских мостах

Начало теории графов как раздела математики связывают с так называемой задачей о кёнигсбергских мостах. Эта знаменитая в своё время задача состоит в следующем.

Семь мостов города Кёнигсберга (ныне Калининград) были расположены на реке Прегольтак, как изображено на рис. 1.15. Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?

Сопоставим плану города граф G, вершины которого соответствуют четырём разделяемым рекой участкам суши A, B, Cи D, а рёбра — мостам. Этот граф изображён на рис. 1.16.

Рисунок 1.15 Рисунок 1.16

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

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

Например, граф, изображённый на рис. 1.17, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода рёбер.

Помимо задачи о кёнигсбергских мостах известен ряд других старинных занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета (рис. 1.18), не отрывая карандаша от бумаги и не повторяя линий.

Рисунок 1.17 Рисунок 1.18

Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов

Возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым? Прежде чем дать полный ответ на вопрос в теореме 1, докажем простую лемму.

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

Доказательство. Если в графе G имеются петли или кратные рёбра, то утверждение очевидно; поэтому предположим, что Gявляется простым графом. Пусть v — произвольная вершина графа G; построим по индукции маршрут

>>> … , выбирая вершину смежной вершине , а для i ? 1 — выбирая смежной и отличной от (существование такой вершины гарантировано условием леммы). Так как Gимеет конечное число вершин, то в конце концов мы придём к вершине, которая уже была выбрана раньше. Предположим, что — первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями , и является требуемым циклом.

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

Доказательство. =>Предположим, что Pявляется эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Pчерез любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Pровно один раз, то каждая вершина должна иметь чётную степень.

<= Проведём доказательство индукцией по числу рёбер в G. В силу связности G, степень каждой вершины не меньше двух, а отсюда, по предыдущей леммы, заключаем, что граф Gсодержит цикл С. Если С проходит через каждое ребро графа G, то доказательство завершено; если нет, то, удаляя из Gрёбра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф Н. Число рёбер в Н меньше, чем в G, и любая вершина в Н по-прежнему имеет чётную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идём по рёбрам цикла С до тех пор, пока не встретим неизолированную вершину графа Н, затем следуем по эйлеровой цепи той компоненты в Н, которая содержит указанную вершину; далее продолжаем путь по рёбрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа Н, и т.д.; заканчивается процесс тогда, когда мы попадём обратно в начальную вершину (см. рис. 1.19).

Рисунок 1.19

Модифицируя данное доказательство, легко получить следующие два результата.

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

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

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