Учитывая случайный однонаправленный граф, я должен найти «ребра узкого места», чтобы перейти от одной вершины к другой. .
То, что я называю «узкими местами» (должно быть название получше!) - Предположим, у меня есть следующий однонаправленный граф:
A
/ | \
B--C--D
| |
E--F--G
\ | /
H
Чтобы добраться от A до H независимо от выбранных ребер пути, необходимо всегда пересекать BE и DG, что создает «узкое место».
Существует ли для этого алгоритм с полиномиальным временем?
править: да, название - «минимальный разрез» для того, что я имел в виду под «краями узких мест».