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

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

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

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

поиск циклов в неориентированном графе
Есть неориентированный граф, степени вершин которого >=2. Нужно найти для выбраной вершины цикл (циклы) содержащий наименьшее количество вершин.
  #2  
Старый 26.01.2009, 05:45
гость

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

Пусть заданная вершина - u, а v - одна из соседних с ней вершин. Удалим из графа ребро u-v и найдем кратчайший путь из u в v, - если такой путь существует, то добавляя в него ребро u-v получим кратчайший простой цикл, содержащий вершины u и v. А перебрав все возможные вершины v, получим кратчайший простой цикл c u.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
кто автор алгоритма для поиска всех циклов в ориентированном графе njuri Графы 4 26.12.2008 10:42
нужно составить алгоритм для поиска циклов в ориентированном графе njuri Работа 0 25.12.2008 18:53
Поиск путей в графе MrFandorin Графы 5 24.04.2008 01:25
Поиск эйлерова цикла в графе,ошибка гость Реализация, исходники, языки 0 21.11.2007 22:40