假设您已经计算了图表上的最大流量G并且您知道图中每条边的流量。从源顶点s，执行一个广度优先搜索 OR 深度优先搜索在原始图上，只遍历那些有流的边少于边缘的容量。将本次遍历中可到达的顶点集表示为S，以及不可到达的顶点T.
获得最小割C，我们只需找到原始图中的所有边G从某个顶点开始S并在某个顶点结束T.
在Topcoder中提供了上述算法的解释/证明。查看以以下文本开头的部分：
流网络中的切口只是将顶点划分为两个集合，我们将它们称为 A 和 B，这样源顶点在 A 中，汇点在 B 中。
我将尝试在 Topcoder 教程中提供相应部分的解释（也只是为了让我温习一下）。
现在，假设我们已经计算了图上的最大流量G，并且我们已经计算了边集C使用上述程序。从这里，我们可以总结出几个事实。
事实 1：源顶点s必须在集合中S，和汇点t必须在集合中T.
否则，顶点s and t必须在同一个集合中，这意味着我们必须找到一条来自s to t仅由流量小于容量的边组成。这意味着我们可以从s to t，因此我们找到了一条增广路！然而，这是一个矛盾，因为我们已经计算了图上的最大流量。因此，源顶点不可能s和汇点t要连接，并且它们必须位于不同的集合中。
事实 2：每条边都从 set 开始S并在设定时结束T必须有流量==容量
我们再次用反证法证明这一点。假设有一个顶点u in S和一个顶点v in T，这样边(u,v) in the 残差网络流量小于容量。通过我们上面的算法，这条边将被遍历，并且顶点v应该在集合中S。这是一个矛盾。因此，这样的边必须具有流量==容量。
事实 3：去除边缘C从图G意味着集合中没有任何顶点的路径S到集合中的任意顶点T
假设情况并非如此，并且存在一些边缘(u,v)连接顶点u in set S到顶点v in set T。我们可以将其分为两种情况：
- 流过边缘
(u,v)小于其容量。但我们知道这会导致顶点v成为集合的一部分S，所以这种情况是不可能的。
- 流过边缘
(u,v)等于其容量。这是不可能的，因为边缘(u,v)将被视为边缘集的一部分C.
因此这两种情况都是不可能的，我们看到删除边缘C从原始图表G确实会导致无路可走的情况S to T.
事实 4：原始图中的每条边G从顶点集开始T但结束于顶点集S必须有流量0
Topcoder 教程的解释在第一次阅读时可能并不明显，以下是我的有根据的猜测，可能是不正确的。
假设存在一些边(x,y) (where x属于顶点集T and y属于顶点集S），使得流过(x,y)大于0。为了方便起见，我们将流过的流量表示为(x,y) as f。这意味着在残差网络，必须存在后向边缘(y,x)有能力f和流动0。由于顶点y是集合的一部分S, 后边缘(y,x)有流量0有能力f > 0，我们的算法将遍历边缘(y,x)并放置顶点x作为顶点集的一部分S。然而，我们知道顶点x是顶点集的一部分T，因此这是一个矛盾。因此，所有边都来自T to S流量必须为0。
有了这 4 个事实，再加上最大流最小割定理 http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem，我们可以得出结论：
最大流量必须小于或等于任何切割的容量。根据事实 3，C是图的切割，因此最大流量必须小于或等于切割的容量C.
事实 4 让我们得出结论，不存在“回流”T to S。这与事实 2 一起意味着该流量完全由来自以下位置的“前向流量”组成：S to T。特别是，所有向前流动必须由切割产生C。该流量值恰好是最大流量。因此，根据最大流最小割定理，我们知道C必须是最小割。
