Матрица М данного графа имеет вид
a b c d e f
1 b c a c c a
2 - e d f d b
3 - - - - - c
В качестве отправной вершины рассмотрим а. Множество S формируется следующим образом:
| Но-мер | Множество S | Комментарии |
| a | Добавляем первую возможную вершину в столбце а (т.е. вершину b). | |
| а,b | Добавляем первую возможную вершину в столбце b (т.е. вершину с) | |
| a,b,c | Первая вершина а в столбце с не является возможной (аÎS), добавляем следующую вершину в столбце (т.е. вершину d). | |
| a,b,c,d | Добавляем вершину f. | |
| a,b,c,d,f | В столбце f нет возможной вершины. Возвращение. | |
| a,b,c,d | В столбце d не существует возможной вершины, следующей за f. Возвращение. | |
| a,b,c | Аналогично предыдущему. Возвращение. | |
| а,b | Добавляем вершину е. | |
| a,b,e | Добавляем вершину с. | |
| a,b,e,c | Добавляем вершину d. | |
| a,b,e,c,d | Добавляем вершину f. | |
| a,b,e,c,d,f | Гамильтонов путь. Дуга (f,a) дает гамильтонов контур. Возвращение. | |
| a,b,e,c,d | Возвращение. | |
| a,b,e,c | Возвращение. | |
| a,b,e | Добавляем вершину d. | |
| a,b,e,d | Добавляем вершину f. | |
| a,b,e,d,f | Добавляем вершину c. | |
| a,b,e,d,f,c | Гамильтонов путь. Путь замыкается дугой (c,a). Возвращение. | |
| a,b,e,d,f | Возвращение. | |
| a,b,e,d | Возвращение. | |
| a,b,e | Возвращение. | |
| а,b | Возвращение. | |
| a | Возвращение. | |
| Æ | Конец поиска. |
В результате работы алгоритма определены гамильтоновы пути m1=[a,b,e,c,d,f], m2=[a,b,e,d,f,c] и контуры [a,b,e,c,d,f,a], [a,b,e,d,f,c,a].
Дата добавления: 2015-04-10; просмотров: 749;