Эйлеровы и гамильтоновы графы
Категория реферата: Рефераты по информатике, программированию
Теги реферата: компьютерные рефераты, инновационная деятельность
Добавил(а) на сайт: Папанов.
Предыдущая страница реферата | 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 | Следующая страница реферата