在图中找到最小割边

Question

给定一个随机无向图，我需要找到“瓶颈边”（编辑：最小割边）以从一个顶点到另一个顶点。

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

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

要独立从A到H，无论选择哪条路径，都必须穿过边BE和DG，因此形成了一个“瓶颈”（编辑：最小割）。

是否有一种多项式时间算法来解决这个问题？

- Noros

---

HE、HF和HG也会被视为瓶颈吗？您有不同的定义吗？ - Aryabhatta

这听起来非常像旅行商问题，只是将距离替换为计算时间。与您的问题特别相关的是瓶颈旅行商问题。 - user688334

你的意思是边缘BE 或者 DG必须总是被遍历吗？ - sawa

sawa：是的，说“BE”或“DG”可能更正确。 - Noros

Answer 1

听起来你需要最小割，即移除最少的边使得图被分成两个部分。 http://en.wikipedia.org/wiki/Minimum_cut

- unbeli

---

这可能就是它了。并使用最大流=最小割 :-) - Aryabhatta

谢谢，是的，最小割！ :) - Noros

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将给我们路径A-B-E-H。 在删除这些边之后，我们仍然能够找到路径A-D-G-H。 删除这些边后，图被划分为可达顶点{A,B,C,D}和不可达{E,F,G,H}。 从每个集合（B-E和D-G）中各取一个顶点的边是瓶颈边。

- hugomg

---

我忘记了是否使用BFS可以直接删除边缘（在这个无权、无向的情况下），而不是做所有有向边缘的事情。有人还记得吗？ - hugomg