double arrow

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


       
 
   
 


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

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

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

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

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

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

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

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




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

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

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







Сейчас читают про: