查找图中的'瓶颈边缘'

给定一个随机单向图，我必须找到'瓶颈边'来从一个顶点到另一个顶点。查找图中的'瓶颈边缘'

我所谓的“瓶颈边缘”（！必须有一个更好的名字） - 假设我有以下的单一方向图：

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

为了从A至H的独立选择的必须始终遍历路径边缘BE和DG，因此造成“瓶颈”。

是否有一个多项式时间算法呢？

编辑：是的，这个名字是'我的意思是女巫的瓶颈'的'最低限度'。

来源

2011-04-27 Noros

HE HF和HG是否也被认为是瓶颈？你有不同的定义吗？ – 2011-04-27 21:19:31

这听起来非常像[旅行推销员问题]（http://en.wikipedia.org/wiki/Travelling_salesman_problem），只是用计算时间替换距离。与你的问题具体相关的是[瓶颈旅行推销员问题]（http://en.wikipedia.org/wiki/Bottleneck_traveling_salesman_problem） – osknows 2011-04-27 21:24:44

你的意思是边缘BE **或** DG必须总是遍历？ – sawa 2011-04-28 12:19:56

听起来就像你需要最小的切割，最小的一组边缘去除将你的图分成两部分。

http://en.wikipedia.org/wiki/Minimum_cut

来源

2011-04-27 21:22:48 unbeli

这可能就是这样。并使用最大流量=最小切:-) – 2011-04-27 21:23:14

谢谢，是的，最低限度它是！ :) – Noros 2011-04-28 20:05:22

你所寻找的是一个cut。给定一个图，剪切是一组边将顶点分割成两个不相交的子集。

假设您试图尽可能缩小切割范围，这是经典的最小切割问题。这是Ford-fulkerson算法的伪代码版本，针对您的案例进行了重新设计（无向图，未加权图）。我很确定它应该可以工作，但我不确定我是否在这里最有效率/惯用。

reorganize your graph into a directed graph, 
    with two directed edges (u->v, v->u) for each original edge (u-v) 

while there is a path P from A to H: 
    (hint: use breadth first search to find paths - long story here) 
    //augment the path P: 
    for each edge (u->v) in P: 
    remove (u->v) from the graph and add (v->u) to it 
    (if v->u isn't there already) 

Label all vertices as reacheable or not reacheable from A. 

The bottleneck edges is the set of edges 
    that connect a reacheable and a unreacheable vertex

例如，你的情况BFS会给我们的路径A-B-E-H。去除这些边缘后，我们仍然能够找到路径A-D-G-H。在删除这些边之后，该图被分割成可重新获得的顶点{A，B，C，D}和不可更新的{E，F，G，H}。每个（B-E和D-G）集具有顶点的边是瓶颈边。

来源

2011-04-27 22:53:36 hugomg

我忘记了如果使用BFS可以让我们直接删除边缘（在这个不加权的，无向的），而不是做所有的定向边缘的东西。有人记得吗？ – hugomg 2011-04-27 22:59:45

查找图中的'瓶颈边缘'

回答

相关问题