2 задачки на графах

[kdm]

Есть две такие задачки:

1) По заданному орграфу и целому числу k требуется определить, существует ли
односвязный подграф, имеющий по меньшей мере k ребер.

2) Найти все возможные пути между двумя вершинами в графе, не пересекающиеся по
вершинам.

Посоветуйте, пожалуйста, чем можно воспользоваться для их решения.

[Brukvalub]

kdm в сообщении #169370 писал(а):

Посоветуйте, пожалуйста, чем можно воспользоваться для их решения.

Например, перебором.

[kdm]

Перебором как-то совсем неоптимально)

Хотелось бы что-нибудь более эффективное.

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

А в первой задачке вообще непонятно мне пока, как искать. Односвязный подграф я так понимаю, это граф имеющий хотя бы одну точку сочленения, как её искать не знаю. Была мысль, что можно найти простой цикл и он будет являться односвязным подграфом, но это , думаю, неверно..

[kdm]

вторая задачка вроде бы через потоки на графах может решаться?ни у кого нет идей?

[kdm]

Первую задачку я все-таки решил) Так что по ней помощи не требуется, а вот по второй ещё надеюсь.