在图表中查找"瓶颈边缘"

Question

给定一个随机的单向图,我必须找到"瓶颈边缘"从一个顶点到另一个顶点.

我称之为"瓶颈边缘"(必须有一个更好的名称!) - 假设我有以下单向图:

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

为了从A到H独立于所选择的路径边缘,必须始终遍历BE和DG,因此产生"瓶颈".

有多项式时间算法吗？

编辑:是的,这个名字是"最小切割",因为我的意思是"瓶颈边缘".

Answer 1

听起来你需要最小的切割,最小的边缘去除将把你的图形分成两部分.

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

Answer 2

你要找的是一个切口。给定一个图，切割是一组边，它将顶点划分为两个不相交的子集。

假设您正在尝试获得尽可能小的切割，这是经典的最小切割问题。这是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 将为我们提供路径 ABEH。删除这些边后，我们仍然能够找到路径 ADGH。删除这些边后，图被划分为可达顶点{A,B,C,D}和不可达顶点{E,F,G,H}。具有来自每个（BE 和 DG）集合的顶点的边是瓶颈边。