找到最小割中的所有边。

Question

让(G，s，t，{c})成为流网络，并让F成为所有边缘e的集合，其中存在至少一个最小割（A，B），使得e从A到B。提供一个多项式时间算法，找到F中的所有边缘。

注意：到目前为止，我知道我需要运行Ford-Fulkerson以使每个边缘都有流量。此外，我知道对于F中的所有边缘，流量f（e）= c（e）。然而，并非G中符合该约束条件的所有边缘都在最小割中。我被卡住了。

- miszu

Answer 1

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

要获取最小割C，我们只需找到原始图G中所有起点位于S中，终点位于T中的边。

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

“流网络中的切割只是将两个集合中的顶点分成A和B，使得源顶点在A中，汇顶点在B中。”

我将尝试解释Topcoder教程中的相应部分（仅供我自己复习）。

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

事实1：源顶点s必须在集合S中，汇顶点t必须在集合T中。

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

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

同样，我们通过反证法来证明这一点。假设在S中有一个顶点u，在T中有一个顶点v，使得在剩余网络中，边(u,v)的流量小于容量。根据我们上面的算法，将遍历此边，并且顶点v应该位于集合S中。这是一个矛盾。因此，这样的边必须具有流量==容量。

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

假设不是这种情况，并且存在某个边(u,v)连接集合S中的顶点u和集合T中的顶点v。我们可以将其分为两种情况：

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

因此，两种情况都是不可能的，我们可以看到从原图 G 中删除边缘集合 C 将确实导致不存在从 S 到 T 的路径。

事实4：原始图 G 中从顶点集 T 开始但结束于顶点集 S 的每条边必须具有流量为 0

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

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

有了这4个事实，加上最大流最小割定理，我们可以得出以下结论：

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

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

- yanhan

---

C必须是最小割，但可能涉及其他最小割中的更多边，并且问题还要求返回这些边。例如，路径图中所有边的容量均为1，则应返回每条边。 - Chris Jones