помогите плиз придумать алгоритм для решения этой задачи :
есть система двусторонних дорог, выбираются А и Б, определить, можно ли удалить три дороги так, чтобы из А было нельзя пройти в Б
ну устрой перебор (3 вложенных цикла), и перебирая вершины (удаляй их) проверяй есть ли путь... (есть ли путь можно проверить по дейкстре например)
Вообще формализовав задачу получаем - можно ли удалить 3 ребра так что бы остались 2 изолированных графа и вершины А и В находились в разных.
Еще задачу можно сформулировать так "Можно ли провести сечение в графе, что бы оно прошло через 3 или менее ребер и вершины оказались с разных сторон...
думаю задача имеет более красивое решение...