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

 

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

Гамильтоновы графы

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

Пример.

x₁x₂x₃x₄, x₁x₂x₄x₃ и x₁x₃x₂x₄ -гамильтоновы цепи;

x₁ x₂ x₄ x₃ x₁ - гамильтонов цикл.

Гамильтонов цикл – гамильтонова цепь, начинающаяся и заканчивающаяся в одной и той же вершине.

Если критерий существования эйлерова цикла очень прост (необходимо, чтобы степени всех вершин были четными), то для гамильтоновых циклов никакого общего правила не найдено. Известен лишь ряд достаточных условий существования гамильтоновых циклов, некоторые из которых приведены в нижеследующих теоремах.

 

Необходимое условие для какого-либо утверждения это любое утверждение, без выполнения которого данное утверждение заведомо неверно.

Достаточное условие – это утверждение, из которого следует данное утверждение.

 

Теорема 1. Если в графе G(x,σ), |x|=n, для любой пары вершин x_i и x_j выполняется условие ρ(x_i) + ρ(x_j) ≥ n-1, то в графе существует гамильтонова цепь.

Если ρ(x_i) + ρ(x_j) ≥ n, то существует гамильтонов цикл.

 

Теорема 2. Если степень каждой вершины удовлетворяет условию ρ(x_i)≥½|x|=n/2, то в графесуществует гамильтонов цикл.

 

Теорема 3. В полном графе с числом вершин ≥ 2 всегда существует гамильтонов цикл.

Теорема 4. В сильносвязном орграфе всегда существует гамильтонов контур.

 

 

Алгоритм Роберта – Флореса поиска гамильтоновых цепей графа

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

a	b	c	d	e	f
b	c	a	c	c	a
-	e	d	f	d	b
-	-	-	-	-	c

По таблице строится дерево всех возможных решений.

Возможные переходы c→a и d→c в первой ветви игнорируем, т.к. тогда получится цикл, не являющийся гамильтоновым. Также поступаем и в дальнейшем.

Гамильтоновы цепи: (a,b,e,c,d,f) и (a,b,e,d,f,c)

На их основе можно построить гамильтоновы циклы, т.к. есть замыкающие дуги c→a и f→a.