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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ориентированный граф)
(Критерий эйлеровости)
Строка 44: Строка 44:
  
 
|proof=
 
|proof=
 +
 +
Докажем эту теорему, используя индукцию по числу вершин <tex>n</tex>.
 +
 
База индукции: <tex>n = 0</tex> цикл существует.
 
База индукции: <tex>n = 0</tex> цикл существует.
При <tex>k < n</tex> доказано.
 
Рассмотрим граф <tex>G = (V, E) </tex> в котором количество вершин с четной степенью больше нуля. Рассмотрим произвольную вершину <tex>u</tex>. Из нее выходит ребро. Пойдем по нему и будем действовать далее также. Таким образом можно дойти до <tex>u</tex> и найти цикл. Выкинем ребра цикла из графа. Первое условие сохранится. Второе может не выполниться, найдём эйлеров цикл в каждой получившейся компоненте связности.
 
  
Восстановить эйлеров цикл исходного графа можно следующим образом: идём по первому циклу, обнаруженному жадным обходом. Каждый раз, когда вершина этого цикла лежит также и на другом цикле в одной из компонент связности, обходим этот цикл. Очевидно, полученный путь будет являться циклом и обходит все рёбра графа.
+
Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.
 +
 
 +
Рассмотрим граф <tex>G = (V, E) </tex> с <tex>n > 0</tex> вершинами, степени которых четны.
 +
 
 +
Допустим, что <tex>v1</tex> и <tex>v2</tex> - вершины графа. Поскольку граф связный, то существует путь из <tex>v1</tex> в <tex>v2</tex>. Поскольку степень <tex>v2</tex> - чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v1</tex>, и эйлеров цикл можно считать построенным. Если <tex>с1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> - подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>c1</tex>. Поскольку <tex>c1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень.
 +
 
 +
Пусть <tex>e</tex> - ребро графа <tex>G'</tex>. Поскольку <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, и у каждой вершины графа <tex>G'</tex> чётная степень, граф <tex>G'</tex> имеет эйлеров цикл. Пусть это цикл <tex>c2</tex>. У <tex>c1</tex> и <tex>c2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в <tex>а</tex>, обойти <tex>c1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>c2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.
 +
 
 
}}
 
}}
  

Версия 21:02, 10 декабря 2011

Эйлеров путь

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


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

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


Эйлеров цикл

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


Эйлеров граф

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


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

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

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

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

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

1. Допустим в графе количество вершин нечетной степени больше двух. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или конечной. Следовательно вершин с нечетной степенью не может быть больше двух. Наше предположение неверно.

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

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

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Доказательство:
[math]\triangleright[/math]

Докажем эту теорему, используя индукцию по числу вершин [math]n[/math].

База индукции: [math]n = 0[/math] цикл существует.

Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.

Рассмотрим граф [math]G = (V, E) [/math] с [math]n \gt 0[/math] вершинами, степени которых четны.

Допустим, что [math]v1[/math] и [math]v2[/math] - вершины графа. Поскольку граф связный, то существует путь из [math]v1[/math] в [math]v2[/math]. Поскольку степень [math]v2[/math] - чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в [math]v1[/math], и эйлеров цикл можно считать построенным. Если [math]с1[/math] является эйлеровым циклом для [math]G[/math], тогда доказательство закончено. Если нет, то пусть [math]G'[/math] - подграф графа [math]G[/math], полученный удалением всех рёбер, принадлежащих [math]c1[/math]. Поскольку [math]c1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень.

Пусть [math]e[/math] - ребро графа [math]G'[/math]. Поскольку [math]G'[/math] имеет менее, чем [math]n[/math] вершин, и у каждой вершины графа [math]G'[/math] чётная степень, граф [math]G'[/math] имеет эйлеров цикл. Пусть это цикл [math]c2[/math]. У [math]c1[/math] и [math]c2[/math] имеется общая вершина [math]a[/math], так как [math]G[/math] cвязен. Теперь можно обойти эйлеров цикл, начиная его в [math]а[/math], обойти [math]c1[/math] , вернуться в [math]a[/math], затем пройти [math]c2[/math] и вернуться в [math]a[/math]. Если новый эйлеров цикл не является эйлеровым циклом для [math]G[/math], продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для [math]G[/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^+ - deg^- = 1[/math], а для другой [math]deg^+ - deg^- = -1[/math].

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

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

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

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