2 Определения.10. Эйлеровы графы

Тропа в графе Gназываетсяэйлеровой, если она включает в себя все ребра графаG.

Замкнутая эйлерова тропа носит название эйлеров турилиэйлеров цикл.

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

Теорме Эйлера

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

Пример

Класс сложности

П

Алгоритм Флери

роблема нахождения эйлерова цикла относится к Р-классу (полиномиальное время).

Нахождение циклов в эйлеровом графе:

1. Проверить, является ли данный граф эйлеровым;

2. Выбрать произвольную начальную вершину графа в качестве текущей вершины; все ребра – непомечены;

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

б) выбор моста (ребра разреза) в качестве текущего ребра необходимо делать только в крайнем случае, когда нет иной возможности.

4. Перейти по выбранному ребру ко второй вершине этого ребра;

5. Повторить 3-4 до тех пор, пока не будут пройдены все вершины, и алгоритм не возвратиться в начальную вершину.

Пример

Шаги алгоритма Флери

Граф с помеченными ребрами

Исходный граф без помеченного ребра

D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



D



C



 B



A

F



E



Выбираем любую произвольную вершину в качестве начальной

(например, вершину F)

 B



A

D



C



F



E



Выбираем ребро {F,C}(произвольный выбор).

Помечаем ребро {F,C}

Переходи в вершину С.

Выбираем ребро {С,D}(произвольный выбор).

Помечаем ребро {C,D}.

Переходим в вершину D.

Выбираем ребро {D,A}(произвольный выбор).

Помечаем ребро {D,A}.

Переходим в вершину А.

Выбираем ребро {A,C}.

(нельзя переходить в В, т.к. ребро {A,B}- мост)

Помечаем ребро {A,C}.

Переходим в вершину С.

Остальные шаги алгоритма очевидны. Эйлеров цикл: F,C,D,A,C,E,A,B,D,F.

Определения

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

Теорема

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

Пример

a

b

c

d

e

Алгоритм

Алгоритм Флери применим и для нахождения открытого пути полуэйлерова графа.

2

Определения

.11. Гамильтоновы графы

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

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

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

Граф G, который содержит гамильтонов цикл, называется гамильтоновым графом.

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