两个任意顶点之间的最小割作为无向未加权图的输入

Question

我有一个无向加权图，我需要找到分隔两组顶点的最小割。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小切割。我想补充一下，权重是正的和分数的。

Stoer–Wagner算法除了在切割的不同一侧保留指定节点外，什么都能做，我很好奇是否有任何方法可以修改SW来做到这一点。

谢谢。

Answer 1

不确定Stoer-Wagner，但解决此问题的另一种方法是使用MaxFlow。

您将一组节点链接到源，另一组链接到具有无限容量的目标。每隔一条边的权重应该为1，然后在生成的图中执行MaxFlow。

完成后，标记剩余网络中仍然可以从源访问的所有节点（上次路径查找运行中访问的节点）。原始图中标记和未标记节点之间的任何边都是最小切割的一部分。