Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Посоветуйте, пожалуйста, чем можно воспользоваться для их решения.
Например, перебором.
kdm
20.12.2008, 22:35
Перебором как-то совсем неоптимально)
Хотелось бы что-нибудь более эффективное.
Во второй задачке, конечно, можно найти все пути из одной вершины в другую и выбрать из них наибольшее кол-во не пересекающихся по вершинам. Но возникает вопрос, как найти ВСЕ пути. Да и оптимально это, пожалуй, не будет.
А в первой задачке вообще непонятно мне пока, как искать. Односвязный подграф я так понимаю, это граф имеющий хотя бы одну точку сочленения, как её искать не знаю. Была мысль, что можно найти простой цикл и он будет являться односвязным подграфом, но это , думаю, неверно..
kdm
21.12.2008, 13:10
вторая задачка вроде бы через потоки на графах может решаться?ни у кого нет идей?
kdm
21.12.2008, 19:44
Первую задачку я все-таки решил) Так что по ней помощи не требуется, а вот по второй ещё надеюсь.