1

令 (G,s,t,{c}) 为流网络，令 F 为所有边 e 的集合，其中至少存在一个最小割 (A,B)，使得 e 从 A 到 B。给出一个多项式时间算法，找出 F 中的所有边。

注意：到目前为止，我知道我需要运行 Ford-Fulkerson，以便每个边缘都有一个流程。此外，我知道对于 F 中的所有边，流 f(e) = c(e)。然而，图 G 中并非所有尊重该约束的边都将处于最小切割中。我被困在这里。

4

1 回答 1

2

假设您已经计算了图上的最大流量，G并且您知道通过图中每条边的流量。从源顶点s，在原始图上执行广度优先搜索或深度优先搜索，并且只遍历那些流量小于边容量的边。将此遍历中可到达的顶点集表示为S，将无法到达的顶点表示为T。

为了获得最小割C，我们只需找到原始图G中从某个顶点 in 开始并在某个顶点 inS结束的所有边T。

Topcoder 中的本教程提供了上述算法的解释/证明。查看以以下文本开头的部分：

流网络中的切割只是将顶点划分为两组，我们称它们为 A 和 B，这样源顶点在 A 中，汇在 B 中。

我将尝试对 Topcoder 教程中的相应部分进行解释（只是为了让我也复习一下）。

现在，假设我们已经计算了一个图上的最大流量，并且我们已经使用上面概述的过程G计算了边的集合。C从这里，我们可以得出几个事实。

事实 1：源顶点s必须在 setS中，sink 顶点t必须在 set 中T。

否则，顶点s和t必须在同一个集合中，这意味着我们必须找到一条从s到的路径，该路径t仅由流量小于容量的边组成。这意味着我们可以从sto推动更多的流量t，因此我们找到了一条增广路径！然而，这是一个矛盾，因为我们已经在图上计算了一个最大流量。因此，源顶点s和汇顶点t不可能连接，它们必须在不同的集合中。

S事实 2：从集合开始到集合结束的每条边T都必须有流 == 容量

我们再次用反证法证明这一点。假设存在一个顶点uinS和一个顶点vin T，使得残差网络(u,v)中的边的流量小于容量。通过我们上面的算法，这条边将被遍历，并且顶点应该在 set 中。这是一个矛盾。因此，这样的一条边必须有流量 == 容量。vS

C事实 3：从图中删除边G将意味着从集合S中的任何顶点到集合中的任何顶点都没有路径T

假设情况并非如此，并且有一些边将 set 中的顶点(u,v)连接到usetS中的顶点。我们可以将其分为两种情况：vT

  1. 通过边缘(u,v)的流量小于其容量。但是我们知道这会导致 vertexv成为 set 的一部分S，所以这种情况是不可能的。
  2. 通过边缘(u,v)的流量等于它的容量。这是不可能的，因为边缘(u,v)将被视为边缘集的一部分C。

因此这两种情况都是不可能的，我们看到C从原始图中删除边G确实会导致没有从S到的路径的情况T。

事实 4：原始图G中从顶点集开始T但在顶点集结束的每条边S都必须有一个流0

Topcoder 教程的解释在第一次阅读时可能并不明显，以下是我的有根据的猜测，可能不正确。

假设存在某条边(x,y)（其中x属于顶点集T，y属于顶点集S），使得流通量(x,y)大于0。为方便起见，我们将流通量表示(x,y)为f。这意味着在残差网络上，必然存在一条(y,x)带容量f和流量的后向边0。由于顶点y是集合的一部分S，后向边具有容量(y,x)流，我们的算法将遍历边并将顶点作为顶点集的一部分。但是，我们知道顶点是顶点集的一部分0f > 0(y,x)xSxT，因此这是一个矛盾。因此，从T到的所有边S的流必须为 0。

有了这 4 个事实，再加上Max-flow min-cut theorem，我们可以得出结论：

  1. 最大流量必须小于或等于任何切割的容量。根据事实 3，C是图的一个割，因此最大流量必须小于或等于割的容量C。

  2. T事实 4 让我们得出结论，从到没有“回流” S。这与事实 2 一起意味着流完全由 fromS到的“正向流”组成T。特别是，所有的正向流都必须来自 cut C。这个流量值恰好是最大流量。因此，根据最大流最小割定理，我们知道C必须是最小割。

于 2014-01-31T06:58:52.567 回答