Матрица М данного графа имеет вид


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; просмотров: 834;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.