Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 25.02.2011, 18:11
Новичок

Отправить личное сообщение для kreedz Посмотреть профиль Найти все сообщения от kreedz
 
Регистрация: 25.02.2011
Сообщений: 2

Как найти вершины какого-либо маршрута графа определённой длины?
По запросам в поисковике всё время выдаёт решение на тему поиск кратчайшего пути, мне это не нужно, мне это будет много.
А нужен всего лишь сабж.
Например, есть граф G = <{1, 2, 3, 4}; {[1,2], (4,2), (1,1), (4,3), [2,3], (3,3)}>
Матрицу смежности обозоначим через A, например.
Требуется узнать: набор вершин для (1,1)-маршрута длиной 3, например.
По картинке это сделать более менее я могу, но препод требует, чтобы было расписано, то как находятся эти самые вершины
В тетради группаша я видел некий способ, в котором как я понял что-то делается со строками и столбцами А, А^2, А^3 ... этого графа.
  #2  
Старый 25.02.2011, 18:34
гocть

 
Сообщений: n/a

У степеней матрицы смежности графа есть следующая интерпретация: ij элемент матрицы A^k есть число путей из i в j длины k.

Соответственно, если интересуют пути из вершины 1 в ее саму длины 3, то сначала проверяешь, что A^3 [1, 1] > 0, потом ищешь вершину x, такую, что 1 смежно с x и A^2 [x, 1] > 0, идешь в нее и ищешь уже путь длины 2 из x в 1, и т.д. и т.п, идея думаю ясна.
  #3  
Старый 25.02.2011, 20:16
Новичок

Отправить личное сообщение для kreedz Посмотреть профиль Найти все сообщения от kreedz
 
Регистрация: 25.02.2011
Сообщений: 2

Спасибо, попробую осмыслить.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Всевозможные циклы проходящие через все вершины графа stranik Графы 1 19.12.2010 19:50
Найти в графе все неповторяющиеся циклы длины 3 aviabunin Графы 1 19.12.2010 19:50
Алгоритм построения графа,степень каждой вершины которого равна 4 tradlede Графы 13 16.11.2009 00:41
[C++] Найти все вершины графа, к которым существует путь заданной длины ALI Реализация, исходники, языки 0 11.05.2008 20:00
найти вершины орграфа гость Графы 2 28.12.2007 01:16