Эйлеровы графы

Дан граф. Требуется найти в нем путь, проходящий по каждому ребру ровно один раз. Начало и конец – в одной вершине.

Такой путь называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом.

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

Лемма. Если степень каждой вершины графа ≥ 2, то граф имеет цикл.

◄Построим путь υ₀, υ₁, …, υ_k, … так что υ_i+1 смежна с υ_i и отлична от υ_i-1. Так как граф конечен, то на некотором шаге построения придем к вершине, выбранной ранее. Пусть υ_k – первая из этих вершин. Тогда часть пути, лежащая между первым и вторым появлением вершины υ_k, и есть искомый цикл.►

Теорема Эйлера. Связный граф является эйлеровым тогда и только тогда, когда каждая его вершина имеет четную степень.

◄Доказательство проводится индукцией по числу ребер.

1. База индукции – простая петля n=1, m=1.

2. Индуктивный переход. Предположим, что в графе с m ребрами и чётными степенями вершин имеется эйлеров путь. Рассмотрим граф G с m+1 ребром. Согласно лемме, в этом графе существует цикл C_k, k>0. Рассмотрим граф, являющийся дополнением данного цикла относительно исходного графа G^² = G\C_k = <V, E\C_k>, G = C_kÇ G^². (Случай k=1 тривиален – G^² имеет m рёбер и). Если граф G^² связен, то он имеет n вершин, степени которых остались чётными и m+1–k ≤ m рёбер, т.е. подпадает под предположение индукции. Если же G^² несвязен, то каждая компонента связности имеет меньше чем m+1–k < m рёбер. Следовательно, по предположению индукции каждая связная компонента является эйлеровой.►

Данное доказательство существования эйлерова цикла можно превратить в конструктивное – т.е. на его основе построить алгоритм нахождения эйлерова цикла в графе.

Построим произвольный цикл в графе и рассмотрим дополнение этого цикла до исходного графа (G^²). Связные компоненты графа G^² имеют общие вершины с циклом (т.к. исходный граф связен) и степени всех вершин по-прежнему имеют четную степень. В каждой компоненте построим эйлеров цикл и объединим их в общий эйлеров цикл. Делается это следующим образом: пойдем по построенному циклу до первой встречи с сочленением с эйлеровым подциклом и пойдем по нему. Пройдем по подциклу и вернемся в цикл. Таким образом построим весь эйлеров цикл в графе.