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

Эйлеров путь

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

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

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

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

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

Эйлеров цикл

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

Эйлеров цикл - замкнутый эйлеров путь.

Эйлеров граф

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

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

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

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

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

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

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

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. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

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

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

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

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