Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Алгоритм поиска гамильтонова цикла в графе
СообщениеДобавлено: 15 дек 2011, 18:59 
Не в сети
Начинающий
Зарегистрирован:
15 дек 2011, 18:34
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

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

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

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи 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, после которого этот объем снова начинает уменьшаться.

И пример, не могу его понять.

Вложения:
2011-12-15 19-54-22.jpg
2011-12-15 19-54-22.jpg [ 274.54 Кб | Просмотров: 153 ]
2011-12-15 19-54-30.jpg
2011-12-15 19-54-30.jpg [ 262.4 Кб | Просмотров: 98 ]
Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю larkuzminova "Спасибо" сказали:
Donnie
 Заголовок сообщения: Re: алгоритм поиска гамильтонова цикла в графе
СообщениеДобавлено: 16 дек 2011, 21:00 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Можно посмотреть книгу Домнина "Элементы теории графов".

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Алгоритм поиска цикла

в форуме Дискретная математика, Теория множеств и Логика

stalker2022

8

183

21 дек 2022, 13:32

Алгоритм поиска в графе

в форуме Дискретная математика, Теория множеств и Логика

Vansoul

7

223

04 апр 2019, 11:52

Алгоритм поиска всех деревьев в графе

в форуме Дискретная математика, Теория множеств и Логика

Aquilo

0

235

02 ноя 2014, 15:47

Гамильтонова цепь в кубическом графе

в форуме Задачи со школьных и студенческих олимпиад

IvanIvanov127

1

323

06 фев 2017, 19:09

Алгоритм поиска корней по Бренту.

в форуме Численные методы

Monk0712

0

348

13 окт 2014, 17:35

Алгоритм поиска кратной медианы графа

в форуме Дискретная математика, Теория множеств и Логика

marik22222

0

341

22 ноя 2014, 18:32

Алгоритм Фужера поиска стандартного базиса

в форуме Линейная и Абстрактная алгебра

Abraziv

0

328

30 апр 2016, 13:46

Алгоритм поиска расстояния с метрикой Громова-Хаусдорффа

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

Natanagar

0

216

18 июн 2022, 19:24

Теория графов. Приближенный алгоритм поиска p-медиан

в форуме Дискретная математика, Теория множеств и Логика

surrexi

0

336

14 июн 2016, 14:23

Имеется ли алгоритм поиска всех элементарных циклов графа?

в форуме Информатика и Компьютерные науки

inek82

0

233

03 июл 2021, 21:53


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 29


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved