2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 2 задачки на графах
Сообщение20.12.2008, 21:26 
Есть две такие задачки:

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

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

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

 
 
 
 
Сообщение20.12.2008, 22:16 
Аватара пользователя
kdm в сообщении #169370 писал(а):
Посоветуйте, пожалуйста, чем можно воспользоваться для их решения.
Например, перебором.

 
 
 
 
Сообщение20.12.2008, 22:35 
Перебором как-то совсем неоптимально)

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

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

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

 
 
 
 
Сообщение21.12.2008, 13:10 
вторая задачка вроде бы через потоки на графах может решаться?ни у кого нет идей? :)

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group