给定一个随机无向图，我必须找到“瓶颈边”（编辑：最小切割边）才能从一个顶点到达另一个顶点。
我所说的“瓶颈边缘”（编辑：最小切割边缘）--
假设我有以下无向图：
A
/ | \
B--C--D
| |
E--F--G
\ | /
H
为了从 A 到 H 独立于所选路径边，必须始终遍历 BE 和 DG，因此形成“瓶颈”（编辑：最小切割）。
有没有多项式时间算法？
听起来你需要最小切割，即删除最少的边集，这会将你的图分成两部分。
http://en.wikipedia.org/wiki/Minimum_cut
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
