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

Строится матрица переходов размера , где 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 не наблюдается. ■