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

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

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

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

Эйлеров путь

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

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

Эйлеров цикл

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

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

Эйлеров граф

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

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

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

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

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] является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.

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

[math]\triangleright[/math]

Аналогично неориентированному графу.

[math]\triangleleft[/math]

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

Источники

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