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

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

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

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

Эйлеров путь

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

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

Эйлеров цикл

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

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

Эйлеров граф

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

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

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

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

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

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

Эйлерова пути нет. Количество вершин нечетной степени больше двух.

Две компоненты связности, одна имеет ребра.

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Ориентированный граф

Теорема:

Ориентированный почти связный граф [math]G = (V, E) [/math] является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.

Источники

1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.