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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм построения эйлерова цикла, эйлерова пути)
(Алгоритм построения эйлерова цикла, эйлерова пути)
Строка 66: Строка 66:
  
 
Запускаем алгоритм от вершины <tex>v</tex>
 
Запускаем алгоритм от вершины <tex>v</tex>
  procedure FindEulerPath (v)
+
  procedure FindEulerPath(v)
  перебрать все рёбра, выходящие из вершины v.
+
    перебираем все рёбра, выходящие из вершины v.
  каждое такое ребро удаляем из графа.
+
      каждое такое ребро удаляем из графа.
  вызываем FindEulerPath из второго конца этого ребра.
+
      вызываем FindEulerPath из второго конца этого ребра.
  добавляем вершину v в ответ.
+
    добавляем вершину v в ответ.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 08:09, 30 ноября 2011

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

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


Эйлеров путь

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


Эйлеров цикл

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


Эйлеров граф

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


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

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

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 в ответ.