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

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

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

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

Эйлеров путь

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

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

Эйлеров цикл

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

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

Эйлеров граф

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

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

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

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

Достаточность: Рассмотрим эйлеров цикл [math]p[/math] в [math]G[/math]. Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени. Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень. Необходимость: Докажем утверждение по индукции. База: Лес из [math]N[/math] деревьев, каждое из 1 вершины. Переход: Рассмотри граф, в котором степени всех вершин четные. В нем найдется простой цикл, т.к. иначе граф является лесом, и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин. Рассмотрим цикл [math]c[/math] такой, что при удалении его ребер не образуется двух компонент связности размера больше 1. Такой всегда существует, т.к. граф блоков и точек сочленения произвольного почти связного графа является деревом, а т.к. все вершины [math]G[/math] имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом. Рассмотрим вершину [math]u[/math] со степенью больше 2. После удаления цикла [math]c[/math] из графа степени всех вершин останутся четными, при этом количество ребер в графе уменьшится. Для [math]G - c[/math], по предположению индукции, существует эйлеров цикл [math]e[/math]. Тогда в [math]G[/math] тоже существует эйлеров обход - сначала обойти цикл [math]c[/math], начиная с вершины [math]u[/math], затем обойти [math]e[/math]. Переход доказан.

[math]\triangleleft[/math]

Следствие

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Источники

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