查找图中的最小割边

Question

给定一个随机无向图，我必须找到“瓶颈边”（编辑：最小切割边）才能从一个顶点到达另一个顶点。

我所说的“瓶颈边缘”（编辑：最小切割边缘）-- 假设我有以下无向图：

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

要独立于所选路径边BE和DG从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）集合的顶点的边是瓶颈边。