|
kdm |
|
|
|
Последний раз редактировалось kdm 21.12.2008, 19:44, всего редактировалось 1 раз.
Есть две такие задачки:
1) По заданному орграфу и целому числу k требуется определить, существует ли
односвязный подграф, имеющий по меньшей мере k ребер.
2) Найти все возможные пути между двумя вершинами в графе, не пересекающиеся по
вершинам.
Посоветуйте, пожалуйста, чем можно воспользоваться для их решения.
|
|
|
|
 |
|
Brukvalub |
|
|
Посоветуйте, пожалуйста, чем можно воспользоваться для их решения. Например, перебором.
|
|
|
|
|
|
kdm |
|
|
|
Перебором как-то совсем неоптимально)
Хотелось бы что-нибудь более эффективное.
Во второй задачке, конечно, можно найти все пути из одной вершины в другую и выбрать из них наибольшее кол-во не пересекающихся по вершинам. Но возникает вопрос, как найти ВСЕ пути. Да и оптимально это, пожалуй, не будет.
А в первой задачке вообще непонятно мне пока, как искать. Односвязный подграф я так понимаю, это граф имеющий хотя бы одну точку сочленения, как её искать не знаю. Была мысль, что можно найти простой цикл и он будет являться односвязным подграфом, но это , думаю, неверно..
|
|
|
|
|
|
kdm |
|
|
вторая задачка вроде бы через потоки на графах может решаться?ни у кого нет идей? 
|
|
|
|
|
|
kdm |
|
|
|
Первую задачку я все-таки решил) Так что по ней помощи не требуется, а вот по второй ещё надеюсь.
|
|
|
|
|
