Метод Роберта и Флореса (перебор-метод для орграфов)

Метод работает с путём, непрерывно продлеваемым до тех пор, пока либо получим Гамильтонов контур, либо ясно, что мы его не получим.

Строят M = {m_ij} k×n, где n – число вершин, k – наибольшая полустепень исхода вершины. Элемент m_ij представляет собой вершину (например (x, q)), для которой в графе G существует дуга (x_j, x_q). Вершины (x, q) во множестве Г(x_j) можно упорядочить произвольно, образовав элементы j-ого столбца матрицы М.

Некоторая вершина (например, x₁) выбирается в качестве отправной и образуется первый элемент множества S, в котором хранятся уже найденные вершины строящегося пути. К множеству S добавляется первая вершина (например, x₂) из столбца x₁, затем к множеству S добавляется первая возможная вершина (пусть x₃) из столбца x₂ и т.д.

Под “возможной” вершиной мы понимаем вершину, ещё не принадлежащую множеству S.

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

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

2. Путь, определяемый последовательностью вершин из множества S, имеет длину (n-1), т.е. является Гамильтоновым.

В этом случае:

1. В графе G существует дуга (x_r, x₁) и поэтому Гамильтонов контур может быть найден;

2. Дуга (x_r, x₁) не существует и не может быть получен Гамильтонов контур.

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

и добавлений к множеству S первой возможной вершины следующей за х_r в столбце х_r-1 матрицы М.

Если не существует никакой возможной вершины в столбце , делается следующий шаг возвращения и т.д.

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

Пример: применение алгоритма Роберта и Флореса.

Рис. 55

Множество S		Комментарии
1		Добавляем первую возможную вершину из множества
2		Добавляем первую возможную вершину из множества
3		Добавляем первую возможную вершину из множества
4		Добавляем первую возможную вершину из множества
5		В множестве нет возможных вершин «возвращение»
6		В множестве нет возможных вершин «возвращение»
7		В множестве нет возможных вершин «возвращение»
8		Добавляем первую возможную вершину из множества
9		Добавляем первую возможную вершину из множества
10		Добавляем первую возможную вершину из множества
11		Добавляем первую возможную вершину из множества
12		Гамильтонов контур, так как дуга «возвращение»
13		В множестве нет возможных вершин «возвращение»
14		В множестве нет возможных вершин «возвращение»
15		Добавляем первую возможную вершину в множество
16		Добавляем первую возможную вершину в множество
17		Добавляем первую возможную вершину в множество
18		Гамильтонов контур, так как дуга «возвращение»
19		Нет возможных вершин «возвращение»
20		Нет возможных вершин «возвращение»
21		Нет возможных вершин «возвращение»
22		Нет возможных вершин «возвращение»
23		Нет возможных вершин «возвращение»
24

Конец поиска, в результате которого мы нашли два Гамильтоновых контура.