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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий эйлеровости)
(Критерий эйлеровости)
Строка 25: Строка 25:
  
 
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
 
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
 +
 +
'''Доказательство:'''
 +
 +
1. Допустим в графе количество вершин нечетной степени больше двух. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или конечной. Следовательно вершин с нечетной степенью не может быть больше двух. Наше предположение неверно.
 +
 +
2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
  
 
[[Файл:not_euler.png|200px|thumb|center| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
 
[[Файл:not_euler.png|200px|thumb|center| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
 
[[Файл:not_euler2.png|200px|thumb|center| Две компоненты связности, одна имеет ребра.]]
 
[[Файл:not_euler2.png|200px|thumb|center| Две компоненты связности, одна имеет ребра.]]
 
'''Доказательство:'''
 
  
 
{{Теорема
 
{{Теорема

Версия 06:29, 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. [math]|deg^+u - deg^-u| = 1[/math].

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

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

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

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