|
|
|
| нужно описать нахождение циклов в графе(часть всей программы), узнать есть ли они и сколько их | |
|
|
|
|
|
|
|
для: avitamin033
(22.05.2007 в 13:14)
| | не понял вопроса... то есть тебе дан ехе-шник а нада найти кол-во циклов в нем? | |
|
|
|
|
|
|
|
для: alex19921992
(23.05.2007 в 12:11)
| | Теория графов - это из дискретной математики. | |
|
|
|
|
|
|
|
для: avitamin033
(22.05.2007 в 13:14)
| | Нужно сделать рекурсивный обход всех возможных путей в графе, помечая узлы какой-либо меткой. Если при этом обходе мы встретим уже помеченный узел, значит мы нашли цикл. Затем можно удалить все ребра, принадлежащие циклу, снять все метки и запустить всю процедуру поновой чтобы найти второй цикл. Так можно продолжать пока не найдем все циклы в графе. | |
|
|
|
|
|
|
|
для: oleg_alexeev
(23.05.2007 в 23:43)
| | не согласен с вами.
>>>Затем можно удалить все ребра, принадлежащие циклу, снять все метки и запустить всю процедуру
а вдруг эти ребра принадлежат какому-то другому циклу? при убирании этих ребер может разорваться какой-нить другой цикл. | |
|
|
|
|
|
|
|
для: alex19921992
(24.05.2007 в 12:12)
| | >> а вдруг эти ребра принадлежат какому-то другому циклу?
Я бы такую ситуацию назвал одним самопересекающимся циклом а не двумя циклами с общими ребрами. Это просто вопрос определения, что такое есть цикл в графе. Тут лучше почитать официальные книжки. | |
|
|
|
|
|
|
|
для: avitamin033
(22.05.2007 в 13:14)
| | Вам какие циклы нужно найти? Потому как в одном графе может быть один цикл (если граф эйлеров), а может и больше одного, если считать простые циклы.
В каком виде задан граф? Матрицей смежности или инцидентности? | |
|
|
|