如何使用最大流算法在图上找到最小割线？

Question

我需要找到图上的最小割线。我一直在读关于流网络的文章，但我所能找到的都是最大流算法，如Ford-Fulkerson，push-relabel等。给定最大流-最小割集定理，是否可以使用这些算法中的一种来使用最大流算法在图上找到最小割集？多么?

到目前为止，我找到的最好的信息是，如果我找到“饱和”边，即流量等于容量的边，这些边对应于最小切割。这是真的吗？对我来说这听起来不是100%正确的。的确，最小割线上的所有边都是饱和的，但我相信也可能有饱和的边在最小割线“路径”之外。

Answer 1

从源顶点开始，沿着残差网络中的边(即，非饱和边和有流的边的后边)进行深度优先搜索，并标记以这种方式可以到达的所有顶点。切割由从标记顶点到未标记顶点的所有边组成。显然，这些边是饱和的，因此没有被遍历。正如您所指出的，可能还有其他饱和边不是最小剪切的一部分。

Answer 2

我不想挑剔，但建议的解决方案并不完全正确。

正确的解决方案：你实际上应该做的是在残差网络Gf (read it up on wikipedia)上的bfs/dfs和标记顶点。然后你可以选择那些带有标记的from-vertex和未标记的to-vertex。

为什么‘跟随不饱和边缘’是不够的：考虑一下，flow算法饱和了边缘，如图所示。我用绿色的“只跟随不饱和边”的方法标记了我正在访问的顶点。显然，唯一正确的最小切割是E-F的边缘，而建议的解决方案也将返回A-D (甚至可能是D-E)。

​

请注意，如果我们改为考虑残差网络，则dfs/bfs将访问顶点D，因为将存在从E到D的边，从而使边E-F唯一具有标记的起始顶点和未标记的终止顶点。

Answer 3

注意:Falk算法既可以用来求最小顶点的最小割，也可以用来求最大顶点的最小割。对于后者，算法节奏应该颠倒，即。从接收器顶点而不是源顶点进行搜索。请参阅相关问题：Network Flow: Adding a new edge