algorithm - 在最小切割中找到所有边缘

Question

设（g，s，t，{c}）为流网络，并设F为所有边E的集合，其中存在至少一个最小割（A，B），使得E从A到B。给出一个多项式时间算法，该算法找到F.中的所有边。
注：到目前为止，我知道我需要运行福特富尔克森，使每个边缘有一个流动此外，我知道对于f中的所有边，流f（e）=c（e）。然而，并非图g中与约束相关的所有边都在最小割集中。我被困在这里了。

Answer 1

假设您已经计算了一个图的最大流，并且您知道通过图中每个边的流。从源顶点G，对原始图执行广度优先搜索或深度优先搜索，并仅遍历流小于边容量的边。将此遍历中可到达的顶点集表示为s，将不可到达的顶点表示为S。
为了获得最小割集，我们只需在原始图中找到从T中某个顶点开始到C中某个顶点结束的所有边。
This tutorial在topcoder中提供了上述算法的解释/证明。请看以下文本开头的部分：
流网络中的一个割只是两组顶点的划分，我们称它们为A和B，这样源顶点在A中，汇在B中。
我将尝试在Topcoder教程中提供相应部分的解释（只是让我也复习一下）。
现在，假设我们已经计算了一个图的最大流，并且我们已经使用上述过程计算了边集从这里，我们可以得出几个事实。
事实1：源顶点G必须在setS中，而汇顶点T必须在setG中。
否则，顶点C和s必须在同一集合中，这意味着我们必须找到一条从S到t的路径，该路径仅由流动小于容量的边组成。这意味着我们可以将更多的流从T推到s，因此我们找到了一条增强路径！然而，这是一个矛盾，因为我们已经计算了图上的最大流因此，源顶点t和汇顶点s是不可能连接的，它们必须在不同的集合中。
事实2：从集合t开始到集合s结束的每个边都必须具有flow==容量
我们再次用矛盾来证明这一点假设t中有一个顶点s和t中有一个顶点S，使得剩余网络中的边T的流量小于容量通过上面的算法，该边将被遍历，顶点u应该在集合S中。这是一个矛盾因此，这样的边必须具有flow==容量。
事实3：从图中删除v中的边意味着没有从集合T中的任何顶点到集合(u,v)中的任何顶点的路径。
假设情况并非如此，并且有一些边v将setS中的vertexC连接到setG中的vertexS。我们可以将其分为两种情况：
通过边缘的流量T小于其容量。但我们知道这会导致顶点(u,v)成为集合u的一部分，所以这种情况是不可能的。
通过边缘的流量S等于其容量。这是不可能的，因为edgev将被视为edge setT的一部分。
因此，这两种情况都是不可能的，我们看到从原始图中删除(u,v)中的边确实会导致从v到S没有路径的情况。
事实4：原始图中从顶点集(u,v)开始到顶点集(u,v)结束的每一条边都必须有C的流。
关于Topcoder教程的解释在第一次阅读时可能不明显，以下是我的一个有根据的猜测，可能是不正确的。
假设存在某种边缘C（其中G属于顶点集S和T属于顶点集G），使得流过T大于0。为了方便起见，我们将流经S的流量表示为0。这意味着在剩余网络上，必须存在向后边缘(x,y)容量x和流T。由于顶点y是集S的一部分，因此后边具有流(x,y)和容量(x,y)，我们的算法将遍历边f，并将顶点(y,x)作为顶点集f的一部分放置。然而，我们知道顶点0是顶点集y的一部分，因此这是一个矛盾。因此，从S到(y,x)的所有边的流必须为0。
根据这4个事实以及Max-flow min-cut theorem，我们可以得出结论：
最大流量必须小于或等于任何切削的容量。事实3，0是图的一个割集，所以最大流必须小于或等于割集的容量。
事实4允许我们得出结论，没有从f > 0到(y,x)的“回流”。这与事实2一起意味着流完全由从x到S的“正向流”组成尤其是，所有的正向流动都必须是由切割x引起的。这个流量值恰好是最大流量。因此，根据最大流最小割定理，我们知道T必须是最小割。