问题描述
由于随机单一方向图,我必须找到瓶颈边缘来从一个顶点到另一个。
Given a random unidirected graph, I must find 'bottleneck edges' to get from one vertex to another.
我称之为瓶颈边缘(必须有一个更好的名字!) -假设我有以下单一方向图:
What I call 'bottleneck edges' (there must be a better name for that!) --suppose I have the following unidirected graph:
A
/ | \
B--C--D
| |
E--F--G
\ | /
H
要从A至H独立选择的道路边缘处和危险品必须始终穿过,因此使一个瓶颈。
To get from A to H independently of the chosen path edges BE and DG must always be traversed, therefore making a 'bottleneck'.
有一个多项式时间的算法呢?
Is there a polynomial time algorithm for this?
编辑:是的,名字是最小割的话是什么意思魔女瓶颈边缘
edit: yes, the name is 'minimum cut' for what I meant witch 'bottleneck edges'.
推荐答案
听起来像是你需要的最小割,边集删除,这将分离你的图成两部分的最低。
Sounds like you need minimum cut, the minimal set of edges removing which will separate your graph into two pieces.
http://en.wikipedia.org/wiki/Minimum_cut
这篇关于寻找“瓶颈边缘”中的图的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!