是否有一种算法可以在无向图中找到分离源和汇的最小割 [英] Is there an algorithm to find minimum cut in undirected graph separating source and sink

问题描述

我有一个边加权无向图和 2 个节点(通常称为源和汇).我需要找到一组权重最小的边，将这 2 个节点分成 2 个弱分量.

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components.

我了解 Ford-Fulkerson 的最大流算法 和他的定理关于有向图上的最大流和最小割关系.

I know about Ford-Fulkerson's maximum flow algorithm and his theorem about maximum flow and minimum cut relation on directed graphs.

我还知道对无向图的 Ford-Fulkerson 最大流算法进行了修改，该算法将每个无向边替换为 2 个相反的有向边，并同时更新流向它们两个.但是有了这个修改，最大流最小割定理似乎不再有效，因为在下面的无向图中，最小割将无法正确确定:

I also know about a modification of Ford-Fulkerson's maximum flow algorithm for undirected graphs, which replaces each undirected edge with 2 opposite directed edges and updates flow to both of them simultaneously. But with this modification, the max-flow-min-cut-theorem seems to not be valid anymore, because on the following undirected graph the minimum cut will not be determined correctly:

nodes: 0, 1, 2, 3
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4
source: 0
sink: 3

最大流量最小切割定理说，最小切割是那些边，流量等于它们的容量，而修改后的 Ford-Fulkerson 是所有边，这显然不是正确的切割.

The max-flow-min-cut theorem says, minimum cut are those edges, which flow is equal to their capacity, and by the modified Ford-Fulkerson that's all the edges, which is obviously not the correct cut.

我找到了一个 Stoer-Wagner 算法来寻找全局最小割 在无向图中，但这不是我想要的，因为这个算法不考虑任何源和汇，并且可以找到一个切割，这让节点在同一个组件中.

I found a Stoer–Wagner algorithm for finding a global minimum cut in undirected graph, but that's quite not the thing i want, since this algorithm doesn't consider any source and sink, and can find a cut, which lets the nodes be in the same component.

有什么算法可以有效地在具有源和汇的无向图中找到最小割，将这两个指定节点分开?我可以以某种方式修改前面提到的算法以使它们适用于我的案例吗?

Is there any algorithm, which can efficiently find a minimum cut in an undirected graph with source and sink, separating these 2 specified nodes? Can i maybe somehow modify the previously mentioned algorithms to make them working for my case?

推荐答案

最大流量最小切割定理说，最小切割是那些边，流量等于它们的容量......

The max-flow-min-cut theorem says, minimum cut are those edges, which flow is equal to their capacity ...

这是不正确的.你已经举了反例.这篇文章中给出了从最大流量中找到最小切割的正确算法.我在这里引用.

This is not correct. You have already given a counterexample. A correct algorithm to find a min cut from a max flow is given in this post. I quote it here.

最小割是将节点分成两组.

The minimum cut is a partition of the nodes into two groups.

一旦找到最大流量，就可以通过创建找到最小割残差图，当从源到所有可达节点，这些节点定义了划分.称这个分区为 A.其余的节点(不可达的)可以称为 B.最小割的大小是原始网络中流动的边的权重之和从 A 中的一个节点到 B 中的一个节点.

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition A. The rest of the nodes (the unreachable ones) can be called B. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in A to a node in B.

所以，正如您所说，您可以将每条边转换为 2 个相反的有向边，计算新图中的最大流量，然后使用上述算法将最大流量转换为最小割.

So, as you said, you can transform each edge into 2 opposite directed edges, compute the max flow in the new graph, then use the algorithm above to transform the max flow to a min cut.

这篇关于是否有一种算法可以在无向图中找到分离源和汇的最小割的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！