32. Эйлеровы и гамильтоновы графы

Цикл графов, содержащий все его рёбра, называется Эйлеровым.

Граф, имеющий Эйлеровый цикл, называется Эйлеровым графом.

Теорема. Для связного графа следующий условия эквивалентны:

1.Граф Эйлеров

2.Любая вершина графа имеет чётную степень

3.Множество рёберможно разбить на простые циклы:U=∪Ui Ui≠ Ui∩Uj=

i

Докажем, что 1=>2=>3=>1.

Докажем, что 1=>2. Предположим, что граф Эйлеров, то есть он имеет цикл, содержащий все рёбра графа. Каждое прохождение вершины вносит двойку в степень вершины, так как каждое ребро встречается 1 раз. Это значит, что степень каждой вершины чётное.

Покажем, что2=>3. Предположим, что граф связен и каждая вершина имеет чётную степень. Множ рёбер графа можно разбить на простые циклы следующим образом: выбераем произвольную вершину i1 и двигаемся от неё по ребру к смежной ей вершине i2. Oт i2 к i3…, выбирая каждый раз новое ребро.

Войдя в вершину по некоторому ребру, мы можем выйти из неё по другому ребру. Так как степень каждой вершины чётная, через конечное число шагов некоторая вершина i2,i3,…,ik,…ik построенного маршрута, который начинается и заканчивается ik, образует простой цикл U1. Удаляем рёбра цикла U1 из графа . Возможно, при этом граф распадётся на компоненты связности. При этом степень каждой вершины останется чётной. Применим данную процедуру к каждой компоненте связности, отличной от изолированной вершины. При этом будут построены циклы U2,…,Ul. Через конечное число шагов граф становится пустым, тем самым множ рёбер будет разбито на простые циклы: Ui=∪Ui

i

Покажем, что 2=>3. Пусть дано разбиение графов на простые циклы. Покажем, что из этих простых циклов можно построить один Эйлеров цикл. Пусть дано множество простых циклов u1,u2,…,ul. Так как граф связный, то можно выделить 2 простых цикла, имеющих общую вершину.

(i1,i2,…,id-1,k,id+1,…,in,i1) (j1,j2,…,jm-1,k,jm+1,…,js,j1)

Склеим эти циклы по общей вершине: (i1,i2,…,id-1,k,jm-1,…,j1,js,…,jm+1,k,id+1,…,in,i1)

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

Простой цикл, содержащий все вершины графа, называется Гамильтоновым.

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

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