Поиск «ребер узких мест» в графе

Учитывая случайный однонаправленный граф, я должен найти «ребра узкого места», чтобы перейти от одной вершины к другой. .

То, что я называю «узкими местами» (должно быть название получше!) - Предположим, у меня есть следующий однонаправленный граф:

    A
  / | \
 B--C--D
 |     |
 E--F--G
  \ | /
    H

Чтобы добраться от A до H независимо от выбранных ребер пути, необходимо всегда пересекать BE и DG, что создает «узкое место».

Существует ли для этого алгоритм с полиномиальным временем?

править: да, название - «минимальный разрез» для того, что я имел в виду под «краями узких мест».

7
задан Noros 28 April 2011 в 20:12
поделиться