如何使用最大流量算法找到图形上的最小割口？ [英] How can I find the minimum cut on a graph using a maximum flow algorithm?

问题描述

我需要找到图形上的最小割线。我一直在阅读有关流动网络的信息，但我能找到的只是最大流动算法，例如Ford-Fulkerson，push-relabel等。给定最大流动最小割定理，是否有可能使用这些算法之一来查找使用最大流量算法在图形上的最小割角？

I need to find the minimum cut on a graph. I've been reading about flow networks, but all I can find are maximum flow algorithms such as Ford-Fulkerson, push-relabel, etc. Given the max flow-min cut theorem, is it possible to use one of those algorithms to find the minimum cut on a graph using a maximum flow algorithm? How?

到目前为止，我发现的最佳信息是，如果我发现饱和边缘，即流量等于容量的边缘，则这些边缘对应于最小切割。真的吗？这听起来对我来说不是100％正确。的确，最小切割的所有边缘都会饱和，但是我相信可能还会有超出最小切割路径的饱和边缘。

The best information I have found so far is that if I find "saturated" edges i.e. edges where flow equals capacity, those edges correspond to the minimum cut. Is that true? It doesn't sound 100% right to me. It is true that all edges on the minimum cut will be saturated, but I believe there might also be saturated edges which are out of the minimum cut "path".

推荐答案

从源顶点开始，沿残差网络中的边（即具有流动的边的非饱和边和边的后边）进行深度优先搜索，并标记所有可以达到了这种方式。切割包括从标记顶点到未标记顶点的所有边。显然，那些边缘是饱和的，因此没有被遍历。如您所述，可能还有其他饱和边不属于最小切割的一部分。

From the source vertex, do a depth-first search along edges in the residual network (i.e., non-saturated edges and back edges of edges that have flow), and mark all vertices that can be reached this way. The cut consists of all edges that go from a marked to an unmarked vertex. Clearly, those edges are saturated and thus were not traversed. As you noted, there might be other saturated edges that are not part of the minimum cut.

这篇关于如何使用最大流量算法找到图形上的最小割口？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！