Эйлеровость графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ориентированный граф)
(Ориентированный граф)
Строка 80: Строка 80:
 
В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:
 
В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:
  
1. Для двух вершин данного графа выполнено <tex>|deg^+u - deg^-u| = 1</tex>.
+
1. Для двух вершин данного графа выполнено
  
 
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
 
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Версия 20:31, 10 декабря 2011

Эйлеров путь

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


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

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


Эйлеров цикл

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


Эйлеров граф

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


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

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

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. Для двух вершин данного графа выполнено

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

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

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

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