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

Эйлеров обход

Определение:

Эйлеров обход - обход графа, посещающий эйлеров путь.

Эйлеров путь

Определение:

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

Эйлеров цикл

Определение:

Эйлеров цикл - эйлеров путь, который является циклом.

Эйлеров граф

Определение:

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

Критерий эйлеровости

Необходимое условия:

1. Количество вершин нечетной степени не превосходит двух.

2. Все компоненты связности кроме, может быть одной, не имеют ребер.

Эйлерова пути нет. Количество вершин нечетной степени больше двух.

Две компоненты связности, одна имеет ребра.

Теорема:

В графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда: 1. Все вершины имеют четную степень. 2. Все компоненты связности кроме, может быть одной, не имеют ребер.

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

[math]\triangleright[/math]

База индукции: [math]n = 0[/math] цикл существует. При [math]k = n[/math] доказано. Рассмотрим граф [math]G = (V, E) [/math] в котором количество вершин с четной степенью больше нуля. Рассмотрим произвольную вершину [math]u[/math]. Из нее выходит ребро. Пойдем по нему и будем действовать далее также. Таким образом можно дойти до [math]u[/math] и найти цикл. Выкинем ребра цикла из графа. Первое условие сохранится. Второе может не выполниться.

[math]\triangleleft[/math]

Следствие

В графе [math]G = (V, E) [/math] существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не имеют ребер.

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

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

Ориентированный граф

Теорема:

Ориентированный почти связный граф [math]G = (V, E) [/math] является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.

Алгоритм построения эйлерова цикла, эйлерова пути

Запускаем алгоритм от вершины [math]v[/math]. Алгоритм будет корректно работать, когда в графе существует эйлеров цикл, то есть степени всех вершин четны.

procedure FindEulerPath(v)
   перебираем все рёбра, выходящие из вершины v.
      каждое такое ребро удаляем из графа.
      вызываем FindEulerPath из второго конца этого ребра.
   добавляем вершину v в ответ.

Сложность алгоритма [math]O(VE)[/math]

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

Полезные ссылки

Ф.Харари Теория графов. глава 7. Обходы графов. Эйлеровы графы.