Алгоритм перебора Робертса и Флореcа

(поиск гамильтонова цикла)

Задача: задан граф G, найти все гамильтоновы циклы исходного графа.

Идея алгоритма.

- выбирается некоторая начальная вершина графа. Пусть исходной будет v₁. Эта вершина образует первый элемент множества S; S = {v₁}.

- множество S на каждом шаге будет хранить уже найденные вершины гамильтоновой цепи. К S добавляется первая вершина в столбце, соответствующем v₁. Пусть эта вершина a.

- затем к S добавляется первая “возможная” вершина в столбце a. Пусть это вершина b. S = {v1, a, b}.

Под “возможной” понимается вершина, которой нет в S.

Существует 2 принципа, препятствующих включению некоторой вершины во множество S.

Пусть множество S имеет вид: S = {v₁, a, b, c … v_r-1, v_r}

1. Если в столбце v_r нет возможных вершин (множество S нельзя расширить).

2. Цепь, определенная последовательностью вершин S имеет длину p – 1, где p – количество вершин графа, т. е. она является гамильтоновой цепью.

В случае 2 тоже 2 варианта.

а) В графе G существует ребро (v_r, v₁), следовательно, найден гамильтонов цикл

б) Ребро (v_r, v₁) не существует, следовательно, гамильтонов цикл не может быть получен.

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

Возвращение состоит в удалении последней включенной вершины из S после чего S примет вид:

S = {v₁, a … v_r-1}

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

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

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

Это значит, что все гамильтоновы циклы найдены.

Алгоритм заканчивает работу.

Пример:

А_G – матрица смежности:

Граф G:

Множество S: Комментарии:

1) S = { v₁} Выбираем начальную вершину графа v₁

2) S = { v₁, v₂} Добавляем первую возможную вершину в столбце v₁ (т.е. вершину v ₂)

3) S = { v₁, v₂, v₃} Первая вершина (v₁) в столбце v₂ не является возможной, т.к. она уже принадлежит множеству S, поэтому добавляем следующую вершину в столбце (т.е. вершину v₃)

4) S = { v₁, v₂, v₃, v₄} Добавляем вершину v₄

5) S = { v₁, v₂, v₃, v₄, v₅} - Г Добавляем вершину v₅ и видим, что это гамильтонова цепь. Дуга (v₅,v₁) дает гамильтонов цикл

6) S = { v₁, v₂, v₃, v₄} Возвращение

7) S = { v₁, v₂, v₃} Возвращение

8) S = { v₁, v₂} Возвращение

9) S = { v₁} Возвращение

10) S = { v₁, v₃} Добавляем вершину v₃

11) S = { v₁, v₃, v₂} Добавляем вершину v₂

12) S = { v₁, v₃} В столбце v₂ нет возможной вершины. Возвращение

13) S = { v₁, v₃, v₄} Добавляем вершину v₄

14) S = { v₁, v₃, v₄, v₅} Добавляем вершину v₅. Дуга (v₅,v₁) дает цикл, но он не является гамильтоновым, т.к. во множестве S отсутствует вершина v₂

15) S = { v₁, v₃, v₄} Возвращение

16) S = { v₁, v₃} Возвращение

17) S = { v₁} Возвращение

18) S = { v₁, v₅} Добавляем вершину v₅

19) S = { v₁, v₅, v₄} Добавляем вершину v₄

20) S = { v₁, v₅, v₄, v₃} Добавляем вершину v₃

21) S = { v₁, v₅, v₄, v₃, v₂} - Г Добавляем вершину v₂ и видим, что это гамильтонова цепь. Дуга (v₂,v₁) дает гамильтонов цикл

22) S = { v₁, v₅, v₄, v₃} Возвращение

23) S = { v₁, v₅, v₄} Возвращение

24) S = { v₁, v₅} Возвращение

25) S = { v₁} Возвращение

26) S = Æ Конец поиска