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

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

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

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

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

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

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

Р1’

 
 

Р2

x0 Р1 x1

Р1’’

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

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

Р3 = Р1’ È Р2 È Р1’’.

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

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

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

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

Лемма:

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

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

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

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

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

3

1

4

6

 

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

 

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

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

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

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

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

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

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