Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | |||
---|---|---|---|---|
larkuzminova |
|
|||
Сдаю курсовую работу по теме: ПОИСК ГАМИЛЬТОНОВА ЦИКЛА В ГРАФЕ. Кто может объяснить алгебраический метод поиска? Теорию так же отправляю. Выручайте. Алгебраический метод построения гамильтоновых циклов Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи 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, после которого этот объем снова начинает уменьшаться. И пример, не могу его понять.
|
||||
Вернуться к началу | ||||
За это сообщение пользователю larkuzminova "Спасибо" сказали: Donnie |
||||
Ellipsoid |
|
|
Можно посмотреть книгу Домнина "Элементы теории графов".
|
||
Вернуться к началу | ||
[ Сообщений: 2 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Алгоритм поиска цикла | 8 |
183 |
21 дек 2022, 13:32 |
|
Алгоритм поиска в графе | 7 |
223 |
04 апр 2019, 11:52 |
|
Алгоритм поиска всех деревьев в графе | 0 |
235 |
02 ноя 2014, 15:47 |
|
Гамильтонова цепь в кубическом графе | 1 |
323 |
06 фев 2017, 19:09 |
|
Алгоритм поиска корней по Бренту.
в форуме Численные методы |
0 |
348 |
13 окт 2014, 17:35 |
|
Алгоритм поиска кратной медианы графа | 0 |
341 |
22 ноя 2014, 18:32 |
|
Алгоритм Фужера поиска стандартного базиса
в форуме Линейная и Абстрактная алгебра |
0 |
328 |
30 апр 2016, 13:46 |
|
Алгоритм поиска расстояния с метрикой Громова-Хаусдорффа
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
0 |
216 |
18 июн 2022, 19:24 |
|
Теория графов. Приближенный алгоритм поиска p-медиан | 0 |
336 |
14 июн 2016, 14:23 |
|
Имеется ли алгоритм поиска всех элементарных циклов графа?
в форуме Информатика и Компьютерные науки |
0 |
233 |
03 июл 2021, 21:53 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 29 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |