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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.12.2011, 23:29
Пользователь

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

алгоритмы по графу
Доброго времени суток!
подскажите где можно почитать про следующие алгоритмы:
1) определения остовного леса максимальной высоты, построенного методом поиска в глубину и методом поиска в ширину
2) поиск циклов, включающих заданную вершину
3) определение периферии взвешенного орграфа на основе алгоритма Флойда
  #2  
Старый 14.12.2011, 11:40
Пользователь

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

что никто не знает?
подскажите хотя бы про нахождения циклов с заданной вершиной
  #3  
Старый 14.12.2011, 14:50
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Все циклы? Фундаментальные? Любой один цикл?
  #4  
Старый 14.12.2011, 15:33
Пользователь

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

Сообщение от MBo Посмотреть сообщение
Все циклы? Фундаментальные? Любой один цикл?
В задании было написано поиск циклов, включающих заданную вершину, я думаю, что всех, а не один...
насчет фундаментальных не знаю, подскажите чем они отличаться будут...
  #5  
Старый 16.12.2011, 00:12
Пользователь

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

подскажите тогда по определению остовного леса максимальной высоты, построенного методом поиска в глубину и методом поиска в ширину...
срочно нужно...
  #6  
Старый 16.12.2011, 09:20
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Из каждой вершины запускается обход в ширину или в глубину - таким образом находим диаметры компонентов связности графа. Обход, при котором найден диаметр, используем для построения остовного дерева - оно будет наибольшей высоты.

По периферии - алг. Флойда строит матрицу кратчайших путей, из неё выбираются вершины с наибольшим эксцентриситетом
  #7  
Старый 16.12.2011, 12:08
Пользователь

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

а у Вас есть подробный алгоритм нахождения Гамельтонавых циклов, может с кодом на С++?
  #8  
Старый 16.12.2011, 14:27
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

можно искать чуть измененным поиском в глубину:
http://rain.ifmo.ru/cat/view.php/the...miltonian-2005
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
алгоритмы на графах гость Задачи 2 10.11.2009 15:54
Алгоритмы из STL Рекрут Сортировка и поиск 3 15.10.2009 21:36
Алгоритмы с возвратом гость Задачи 2 28.09.2008 01:38
Алгоритмы поиска kilobait Графы 2 02.04.2008 05:09
Алгоритмы решения СЛУ LMZ Математические алгоритмы 3 16.01.2008 22:04