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

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

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

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

Эйлеров путь

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

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

Эйлеров цикл

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

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

Эйлеров граф

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

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

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

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

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

База индукции: [math]n = 0[/math] цикл существует. При [math]k \lt 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] существует эйлеров цикл тогда и только тогда, когда: 1. Входная степень любой вершины равна ее выходной степени. 2. Все компоненты слабой связности кроме, может быть одной, не имеют ребер.

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

[math]\triangleright[/math]

Доказательство аналогично случаю неориентированного графа.

[math]\triangleleft[/math]

Следствие

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

1. [math]|deg^+u - deg^-u| = 1[/math].

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

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

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

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

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

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

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

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

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

• Ф.Харари Теория графов. глава 7. Обходы графов. Эйлеровы графы.
• Нахождение эйлерова пути
• Алгоритм построения Эйлерова цикла