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

Эйлеров путь

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

Путь [math]P[/math] [math]u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow ...\rightarrow u_{k-1}u_k \rightarrow u_k[/math] в графе [math]G = (V, E)[/math] называется эйлеровым, если [math]P[/math] содержит все ребра [math]G[/math], причем каждое - только один раз.

Эйлеров цикл

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

Цикл [math]C[/math] [math]u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow ...\rightarrow u_ku_0\rightarrow u_0[/math] в графе [math]G = (V, E)[/math] называется Эйлеровым, если [math]C[/math] содержит все ребра [math]G[/math], причем каждое - только один раз.

Эйлеров граф

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

Граф [math]G = (V, E)[/math] называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым.

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

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

Неориентированный граф назовем почти связным, если все его компоненты связности, кроме, быть может, одной, имеют размер 1. Ориентированный граф назовем почти связным, если все его компоненты слабой связности, кроме, быть может, одной, имеют размер 1.

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

Теорема:

Неориентированный почти связный граф [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]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 г.