0 / 0 / 0
Регистрация: 08.05.2011
Сообщений: 48
1

Алгебраический алгоритм поиска гамильтонова цикла в графе.

15.12.2011, 21:24. Показов 4553. Ответов 2
Метки нет (Все метки)

ребята, может кто-нибудь помочь?очень надо
сдаю курсовую работу по теме ПОИСК ГАМИЛЬТОНОВА ЦИКЛА В ГРАФЕ
кто может объяснить алгебраический метод поиска? теорию так же отправляю
выручайте


Алгебраический метод построения гамильтоновых циклов

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x1, x2, … ,xk-1, xk определяется как выражение вида x2*x3* … xk-1, не содержащее две концевые вершины x1 и xk. «Модифицированная матрица смежности» B=[β(i,j)] — это (n×n)- матрица, в которой β(i,j) — xj, если существует дуга из xi в xj и нуль в противном случае. Предположим теперь, что у нас есть матрица PL = [pL(i ,j)], где pL(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами xi и xj для xi≠xj. Положим pL(i,i)=0 для всех i. Обычное алгебраическое произведение матриц определяется как
B*PL=P’L+1=[p’L+1(s,t)]

т.е. p’L+1(s,t) является суммой внутренних произведений всех цепей из xs в xt длины l+1. Так как все цепи из xk в xt, представленные внутренними произведениями из pL(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в pL(k,t) содержат вершину xs. Таким образом, если из p’L+1(s,t) исключить все слагаемые, содержащие xs (а это можно сделать простой проверкой), то получим pL+1(s,t). Матрица PL+1=[pL+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.
Вычисляя затем B*PL+1, находим PL+2 и т.д., пока не будет построена матрица Pn-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*Pn-1 (все диагональные элементы этой матрицы одинаковые).
Очевидно, что в качестве начального значения матрицы P (т.е. P1) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.
Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы PL будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы PL, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.


и пример
не могу его понять
Миниатюры
Алгебраический алгоритм поиска гамильтонова цикла в графе.   Алгебраический алгоритм поиска гамильтонова цикла в графе.  
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.12.2011, 21:24
Ответы с готовыми решениями:

Алгоритм поиска сечений в графе.
Привет всем кто на форуме. Может кто объяснить алгоритм поиска сечений в графе. имеются пути,...

Найти минимальный гамильтонова цикла
Найти минимальный гамильтонова цикла с помощью алгоритма Литтла по заданной матрице стоимостей.

Поиск гамильтонова цикла в графе
ПОмогите плиииз!!! Написать программу поиска гамильтонова цикла в графе

Поиск гамильтонова цикла в графе
Написать программу гамильтонова цикла в графе для PascalABC Помогите пожалуйста Добавлено...

2
0 / 0 / 0
Регистрация: 08.05.2011
Сообщений: 48
15.12.2011, 21:49  [ТС] 2
может кто-нибудь???очень нужно до завтра, выручайте
0
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
28.11.2012, 09:07 3
Алгоритм 2 Поиск гамильтоновых циклов
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2012, 09:07
Помогаю со студенческими работами здесь

Поиск гамильтонова цикла в графе
Написать программу поиска гамильтонова цикла в графе.

Поиск гамильтонова цикла в ориентированном графе
Честно пытался искать по форуму и не только, но так толком ничего и не нашел :\ Необходимо узнать,...

Алгоритм поиска слова в графе
Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в...

Алгоритм поиска слова в заданном Графе
Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru