Форум: Форум C++Разное
Новые темы: 00
MySQL на примерах. Авторы: Кузнецов М.В., Симдянов И.В. C++. Мастер-класс в задачах и примерах. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель PHP 5 / 6 (3 издание). Авторы: Кузнецов М.В., Симдянов И.В. PHP 5/6. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. PHP. Практика создания Web-сайтов (второе издание). Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Форум C++

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Помогите с графами
 
 автор: avitamin033   (22.05.2007 в 13:14)   письмо автору
 
 

нужно описать нахождение циклов в графе(часть всей программы), узнать есть ли они и сколько их

  Ответить  
 
 автор: alex19921992   (23.05.2007 в 12:11)   письмо автору
 
   для: avitamin033   (22.05.2007 в 13:14)
 

не понял вопроса... то есть тебе дан ехе-шник а нада найти кол-во циклов в нем?

  Ответить  
 
 автор: Саня   (24.05.2007 в 11:59)   письмо автору
 
   для: alex19921992   (23.05.2007 в 12:11)
 

Теория графов - это из дискретной математики.

  Ответить  
 
 автор: oleg_alexeev   (23.05.2007 в 23:43)   письмо автору
 
   для: avitamin033   (22.05.2007 в 13:14)
 

Нужно сделать рекурсивный обход всех возможных путей в графе, помечая узлы какой-либо меткой. Если при этом обходе мы встретим уже помеченный узел, значит мы нашли цикл. Затем можно удалить все ребра, принадлежащие циклу, снять все метки и запустить всю процедуру поновой чтобы найти второй цикл. Так можно продолжать пока не найдем все циклы в графе.

  Ответить  
 
 автор: alex19921992   (24.05.2007 в 12:12)   письмо автору
 
   для: oleg_alexeev   (23.05.2007 в 23:43)
 

не согласен с вами.
>>>Затем можно удалить все ребра, принадлежащие циклу, снять все метки и запустить всю процедуру
а вдруг эти ребра принадлежат какому-то другому циклу? при убирании этих ребер может разорваться какой-нить другой цикл.

  Ответить  
 
 автор: oleg_alexeev   (24.05.2007 в 14:04)   письмо автору
 
   для: alex19921992   (24.05.2007 в 12:12)
 

>> а вдруг эти ребра принадлежат какому-то другому циклу?

Я бы такую ситуацию назвал одним самопересекающимся циклом а не двумя циклами с общими ребрами. Это просто вопрос определения, что такое есть цикл в графе. Тут лучше почитать официальные книжки.

  Ответить  
 
 автор: Саня   (24.05.2007 в 11:58)   письмо автору
 
   для: avitamin033   (22.05.2007 в 13:14)
 

Вам какие циклы нужно найти? Потому как в одном графе может быть один цикл (если граф эйлеров), а может и больше одного, если считать простые циклы.
В каком виде задан граф? Матрицей смежности или инцидентности?

  Ответить  
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования