Никто не подскажет как в неориентированном графе можно найти цикл максимальной длинны, включающий заданную вершину?
Заранее спасибо!

Ну дык... поиск в глубину из этой вершины...

Действительно, это стандартный алгоритм на графах, описаный в любой книге по данной тематике. Вот, если не ошибаюсь, примеры:
http://algolist.ru/maths/graphs/maxflows/

SoWa
Я извиняюсь, а при чём тут потоки? 

Silent
Поясните пожалуйста подробнее.
Вот например граф:
1-2, 2-3, 3-4, 4-1, 2-7, 3-7, 6-7, 5-6, 4-5.
И пусть дфс пойдёт так, что получится такое дерево обхода: 1-2-3-4-5-6-7, соответственно будут обратные рёбра 1-4, 2-7, 3-7.
Как отсюда цикл длиннейший доставать (а ответом будет гамильтонов цикл 1-4-5-6-7-3-2-1)?

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

maxdiver, насколько я помню, задача о поиски максимального цикла, в отличие от поиска минимального, не является тривиальной задачей, а является как раз np-полной. Говоря по-русски, пахнет полным перебором. Не всегда же есть гамильтонов цикл.

Earnest, ну так и я о том же 

Добавлено @ 17:37

Я подумал, что этой фразы достаточно, чтобы ни у кого не осталось сомнений в том, что задача ТС является NP-полной.

(хотя сначала я сам чуть не поверил в алгоритм с дфсом  )

Это сообщение отредактировал(а) maxdiver - 19.12.2008, 17:38

Ага, так бывает, когда заявляют с таким апломбом, а ты помнишь смутно...
Я, честно сказать, перепутала тебе с magicfa (тоже на ma-...).
Что касается автора, т.е. magicfa, есть сомнения, что тебе нужно решать именно такую задачу. Скорее всего, возможны другие подходы. Разве что это прямое задание от преподавателя.