Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

В случае 2) возможны следующие случаи:
В графе G существует дуга (xr,x1), и поэтому найден гамильтонов цикл.
Дуга (xr,x1) не существует и не может быть получен никакой гамильтонов цикл.

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

Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1,a,b,c, … ,xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т.д.

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

Рассмотрим пример поиска гамильтонова цикла в графе переборным методом
Робертса и Флореса.

Пример:

[pic]

"2"

1) S = {1}

2) S = {1, 2}

3) S = {1, 2, 3}

4) S = {1, 2, 3, 4}

5) S = {1, 2, 3, 4, 5} - Г 4>3 4>5

6) S = {1, 2, 3, 4}

7) S = {1, 2, 3} 3>1 3>2 3>4

8) S = {1, 2}

9) S = {1}

"3"

10) S = {1, 3} 3>2

11) S = {1, 3, 2} 2>1

12) S = {1, 3} 2>3

13) S = {1, 3, 4} 3>4 4>5

14) S = {1, 3, 4, 5, 4} 5>нет

15) S = {1, 3, 4}

16) S = {1, 3}

Рекомендуем скачать другие рефераты по теме: доклад на тему культура, реферат н.





Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата