Гамильтоновы графы. Метод Робертса – Флореса

Простая цепь называется гамильтоновой.

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

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

Теорема Дирака (достаточное условие гамильтоновости графа)

Если граф является связным и степень каждой вершины удовлетворяет неравенству

где - ближайшее целое число, то граф является гамильтоновым.

В орграфе рассматривают гамильтонов путь и гамильтонов контур.

Рассмотрим задачу построения гамильтонового контура в заданном графе.

Метод перебора Робертса – Флореса

Строится матрица переходов размера , где k – число строк матрицы М, равное наибольшей полустепени исхода вершины; п – число столбцов, равное количеству вершин графа (каждому столбцу взаимно однозначно соответствует вершина графа ) и

.

Вершины можно упорядочить произвольно, образовав элементы j – го столбца матрицы М.

При построении гамильтоновой пути берется первая вершина, соответствующая какому – либо столбцу матрицы М (например, вершина а ). Затем к пути добавляется первая возможная вершина (например, b ) из этого столбца, затем – следующая возможная вершина с в столбце b и т.д.

Под возможной вершиной понимается вершина, еще не принадлежащая строящемуся гамильтоновому пути S.

На шаге r будем иметь путь .

Существует две причины, препятствующие включению очередной вершины:

1. В столбце v_r нет возможной вершины;

2. Путь, определяемый кортежем S , имеет длину п , т.е. является гамильтоновым. Тогда

а) существует дуга (v_r , a) в графе G , следовательно, найден гамильтонов контур;

б) не существует дуги в графе G , следовательно, гамильтонов контур не может быть получен.

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

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

Аналогично метод используется для построения гамильтонова цикла.

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

a b c d e

.

□ Так как матрица смежности несимметричная, то заданный граф G является ориентированным. Граф G показан на рис. 5.3

Рис. 5. 3

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

a b c d e

Для построения гамильтонового контура возьмем, например, вершину a . В соответствующем столбце стоят возможные вершины b и d , возьмем, например, вершину b . В столбце b возможные вершины d и e , возьмем e . В столбце е возьмем вершину с . В столбце с возможными вершинами являются b и е . Обе эти вершины уже задействованы в строящемся контуре. Значит, удаляем вершину с и возвращаемся к столбцу е . В этом столбце стоит еще одна возможная вершина – а , но она также задействована в строящемся контуре. Следовательно, удаляем вершину е и возвращаемся к вершине b . В столбце b возьмем оставшуюся возможную вершину d . В столбце d одна возможная вершина с . В столбце с вершина b задействована в контуре, значит берем вершину е .

Все вершины графа задействованы в построении контура. Следовательно, гамильтонов путь построен:

.

Для построения гамильтонового контура осталось в столбце е взять вершину а . Гамильтонов контур построен :

.

Этот контур выделен на рис. 5. 3.

Аналогично можно построить еще один гамильтонов контур

.

Других гамильтоновых контуров в заданном графе G не наблюдается. ■