给定一个随机的单向图,我必须找到"瓶颈边缘"从一个顶点到另一个顶点.
我称之为"瓶颈边缘"(必须有一个更好的名称!) - 假设我有以下单向图:
A
/ | \
B--C--D
| |
E--F--G
\ | /
H
为了从A到H独立于所选择的路径边缘,必须始终遍历BE和DG,因此产生"瓶颈".
有多项式时间算法吗？
编辑:是的,这个名字是"最小切割",因为我的意思是"瓶颈边缘".