Помощь - Поиск - Пользователи - Календарь
Полная версия: графы!
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
makcblmoff
помогите плиз придумать алгоритм для решения этой задачи :
есть система двусторонних дорог, выбираются А и Б, определить, можно ли удалить три дороги так, чтобы из А было нельзя пройти в Б
Altair
ну устрой перебор (3 вложенных цикла), и перебирая вершины (удаляй их) проверяй есть ли путь... (есть ли путь можно проверить по дейкстре например)

Вообще формализовав задачу получаем - можно ли удалить 3 ребра так что бы остались 2 изолированных графа и вершины А и В находились в разных.

Еще задачу можно сформулировать так "Можно ли провести сечение в графе, что бы оно прошло через 3 или менее ребер и вершины оказались с разных сторон...

думаю задача имеет более красивое решение...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.