найти все циклы в графе определённой длины

 
0
 
Алгоритмы
ava
mrgloom | 08.02.2013, 15:07
найти все простые циклы в неориентированном графе определённой длины

http://sovietov.com/txt/triangle/triangle.html
тут для циклов размером 3.

для размера 4 будет уже 4 цикла for и т.д. может можно как то в общем виде написать?
Ответы (5)
ava
baldina | 08.02.2013, 15:01 #
используй поиск в глубину с возвратом при достижении заданной длины.
ava
mrgloom | 08.02.2013, 17:24 #
а как избежать повторов? т.е. я из одной вершины могу пойти по часовой и против часовой по циклу.
всё равно из какой вершины начинать обход?

ava
baldina | 08.02.2013, 17:56 #
если это поиск в глубину, повторов не будет: пройденные вершины помечаются
ava
mrgloom | 11.02.2013, 15:04 #
мне оказывается надо найти элементарные циклы в графе.

http://dl.dropbox.com/u/8841028/panorama/3_.PNG

и опять же  допустим имеем полный граф 4 вершины мы идем в глубину получаем последовательность 1-2-3-4 и получили 1 цикл и пометили все вершины, а на самом то деле там 5 циклов.
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить