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

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

а) Необходимость.

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

б) Достаточность.

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

Если же в Р₁ содержатся не все ребра графа Г, то удалим из него все ребра цикла Р₁, получая граф Г₁. Все вершины графа Г₁ будут иметь четную степень, как и все вершины исходного графа Г. В силу связности исходного графа Г, существует вершина х₁, входящая одновременно и в цикл Р₁ и в граф Г₁ (см. рисунок 4.21).

Р ₁^’

Р ₂

x₀ Р ₁ x₁

Р ₁^’’

Рисунок 4.21– Граф Г

Тогда, начиная с этой общей вершины х₁, можно построить цикл Р₂ в графе Г₁ аналогично тому, как был построен цикл Р₁. Очевидно, объединив два цикла Р₁ и Р₂, можно получить новый цикл Р₃:

Р₃ = Р ₁^’ È Р₂ È Р ₁^’’ _.

Этот цикл будет проходить, начиная с вершины х₀, путь Р ₁^’ до вершины х₁, далее - цикл Р₂ снова в вершину х₁ и затем – путь Р ₁^’’ в вершину х₀. Если цикл Р₃ не будет элеровым, то, проделав аналогичные построения, можно получить цикл с еще большим количеством ребер, продолжая процесс до построения эйлерова цикла. Он непременно будет построен в силу конечности исходного графа Г.

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

Таким образом, решая задачу о кенигсбергских мостах, рассматривая граф на рисунке 10.1.2, можно заметить, что степени вершин A, B, C, D равны соответственно 5, 3, 3, 3 являются нечетными. Т.е. в данном графе эйлерова цикла нет.

Эйлеровы графы встречаются достаточно редко.

Лемма:

В любом графе число вершин нечетной степени четно.

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

По теореме Эйлера = 2 m, т.е. сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна. Значит, их четное число.

4.6.2 Алгоритм Флёри нахождения эйлерова цикла

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

3

1

4

6

Рисунок 4.22 – Граф с эйлеровым циклом

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

Нахождение эйлерова цикла в графе можно осуществить с помощью алгоритма Флёри:

1. Начиная с произвольной вершины х₀ исходного графа Г₀, присваиваем любому инцидентному ей ребру (х₀, х₁) номер 1. Удаляем ребро (х₀, х₁) из множества ребер графа Г₀ , получая граф Г₁ . Переходим в следующую вершину х₁.

2. Пусть х_k — вершина, в которую мы пришли после очередного шага нумерации ребра, получившего номер k. Для дальнейшей нумерации выбираем любое ребро графа Г_k, инцидентное вершине х_k, с учетом следующего правила: ребра, удаление которых из графа Г_k повлечет нарушение его связности, выбираются только тогда, когда другой выбор осуществить нельзя.

3. Алгоритм заканчивает свою работу, когда получен цикл, т.е. выбрано ребро (х, х₀), где х - некоторая вершина графа Г₀.

Иначе – повторяем пункт 2.

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

Дата добавления: 2014-01-06