给定一个随机的单向图，我必须找到瓶颈边才能从一个顶点到另一个顶点。
我称之为“瓶颈边缘”（必须有一个更好的名称！）--
假设我有以下单向图：
A
/ | \
B--C--D
| |
E--F--G
\ | /
H
要从a到h独立于所选路径的边be和dg必须始终被遍历，因此形成“瓶颈”。
有多项式时间算法吗？
编辑：是的，我说的“瓶颈边缘”的名字是“最小切割”。
最佳答案
听起来你需要最小割集，最小边集移除，这将把你的图分成两部分。
http://en.wikipedia.org/wiki/Minimum_cut