graph-theory - 如何使用最大流量算法在图上找到最小割？

Question

我需要在图表上找到最小切割。我一直在阅读有关流网络的文章，但我能找到的只是最大流算法，例如 Ford-Fulkerson、push-relabel 等。鉴于最大流-最小切割定理，是否可以使用其中一种算法来找到使用最大流算法的图上的最小切割？如何？

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

score 48 · Accepted Answer

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

score 35 · Accepted Answer

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

正确的解决方案：您实际上应该做的是残差网络 Gf上的 bfs/dfs （在 wikipedia 上阅读）并标记顶点。然后你可以选择那些带有标记的从顶点和未标记的顶点。

为什么“跟随不饱和边缘”是不够的：考虑一下，流算法使边缘饱和，如图所示。我用绿色标记了我正在访问的顶点“仅遵循不饱和边缘”的方法。显然，唯一正确的最小切割是来自 EF 的边缘，而建议的解决方案也将返回 AD（甚至可能是 DE）。

请注意，如果我们考虑残差网络，则 dfs/bfs 将访问顶点 D，因为从 E 到 D 会有一条边，从而使边 EF 成为唯一具有标记的从顶点和未标记的边到顶点。

score 6 · Accepted Answer

因此，给出如何获得最小切割的确切过程：

运行 Ford-Fulkerson 算法以找到最大流量并获得残差图¹。
在残差图上运行 BFS以在残差图中找到从源可到达的顶点集（考虑到您不能在残差图中使用容量为 0 的边）。重要提示：您必须在残差图中使用反向边来找到正确的可到达顶点集！！！（见这个算法）
原始图中从可达顶点到不可达顶点的所有边都是最小割边。打印所有这些边缘。

¹图，其中边的容量定义为原始容量减去其流量（来自最大流量网络的流量）。

score 1 · Accepted Answer

注意：Falk 的算法可用于找到具有最小顶点和最大顶点的最小割。对于后者，算法应该颠倒过来，即。从汇点而不是源点搜索。请参阅相关问题：网络流：添加新边缘

score 1 · Accepted Answer

一种理解方式是，让我们将割定义为两个集合 S 和 T，它们分别包括 s 和 t。

现在，在残差网络中添加 S 中从 s 可到达的所有顶点，并将剩余边放入 T 中。这将是一个切割。

其次，可以通过将所有从 t 可到达的顶点放入残差网络中并将剩余的顶点放入 S 中来形成切割。

观看此视频，了解我们如何找到可从 s 和 t 到达的顶点。

score 0 · Accepted Answer

计算出最大流量后，我们可以搜索边(u,v)，使得在残差图中，在残差图中有一条边 from vtou和f(v,u) = c(u,v)[表示边饱和]

在筛选出这些边之后，我们可以(u,v)使用残差图中不存在从 u 到下沉 t 的路径的标准来选择这些边。如果满足这个条件，那么这些边就构成了(S,T)切割的一部分

该算法的运行时间可能为O(E) * O( V + E ) = O( E^2 )

score 0 · Accepted Answer

我认为这是其他人所说的，但我发现不清楚，所以这是我的解释：

从源节点开始，对图进行泛洪填充，仅沿着具有剩余容量的边行进，标记每个访问过的顶点。您可以为此使用 DFS。回想一下，来自顶点的后边具有剩余容量 - 等于沿前边的流量（即 r(u, v) = 边 (u, v) 的剩余容量，r(v, u) = flow(u ，五））。

实际上，这决定了图形 ST 割的 S 部分。

最小切割现在将是一组边，这样一个顶点从上面的洪水填充中标记出来，而另一个顶点没有标记。这些将是没有剩余容量的边（否则您将在 DFS 中遍历它们），并一起形成最小切割。

去除这些边后，这组未标记的顶点将形成切割的 T 部分。

7 回答 7