在最小切割中找到所有边缘 [英] Find all edges in min-cut

问题描述

让（G，s，t，{c}）为流动网络，令F为所有边缘e的集合，对于这些边缘e至少存在一个最小割点（A，B），使得e来自A给出一个可以找到F中所有边的多项式时间算法。

Let (G,s,t,{c}) be a flow network, and let F be the set of all edges e for which there exists at least one minimum cut (A,B) such that e goes from A to B. Give a polynomial time algorithm that finds all edges in F.

注意：到目前为止，我知道我需要运行Ford-Fulkerson，以便每个边都有一个流。而且我知道对于F中的所有边，流f（e）= c（e）。但是，图G中并非所有遵守该约束的边都将处于最小切割状态。我被困在这里。

NOTE: So far I know I need to run Ford-Fulkerson so each edges has a flow. Furthermore I know for all edges in F, the flow f(e) = c(e). However not all edges in a graph G which respects that constraint will be in a min-cut. I am stuck here.

推荐答案

假设您已经计算了图 G ，您就会知道图形中每个边的流量。在源顶点 s 中，对原始图形执行宽度优先搜索或深度优先搜索，仅遍历那些流量小于的边缘。将遍历中可到达的顶点集表示为 S ，将不可访问的顶点表示为 T 。

Suppose you have computed a max flow on a graph G and you know the flow through every edge in the graph. From the source vertex s, perform a Breadth First Search OR Depth First Search on the original graph and only traverse those edges that have flow less than the capacity of the edge. Denote the set of vertices reachable in this traversal as S, and unreachable vertices as T.

要获得最小切割量 C ，我们只需在原始图形 G 在 S 的某个顶点开始，在 T 的某个顶点结束。

To obtain the minimum cut C, we simply find all edges in the original graph G which begin at some vertex in S and end at some vertex in T.

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

This tutorial in Topcoder provides an explanation / proof of the above algorithm. Look at the section beginning with the following text:

在流网络中进行切割只是将顶点分为两组，让我们称它们为A和B，这样的方式是源顶点在A中，宿在B中。

A cut in a flow network is simply a partition of the vertices in two sets, let's call them A and B, in such a way that the source vertex is in A and the sink is in B.

我将尝试提供对Topcoder教程中相应部分的解释（我也要对此进行梳理）。

I shall attempt to provide an explanation of the corresponding section in the Topcoder tutorial (just for me to brush up on this as well).

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

Now, suppose that we have computed a max flow on a graph G, and that we have computed the set of edges C using the procedure outlined above. From here, we can conclude several facts.

否则，顶点 s 和 t 的顶点必须位于同一位置集合，这意味着我们必须找到从 s 到 t 的路径，该路径仅包含流量小于容量。这意味着我们可以将更多的流量从 s 推到 t ，因此，我们找到了一条扩展之路！但是，这是一个矛盾，因为我们已经在图形上计算了最大流量。因此，源顶点 s 和宿顶点 t 是不可能连接的，它们必须位于不同的集合中

Otherwise, vertices s and t must be in the same set, which means that we must have found a path from s to t consisting only of edges that have flow less than capacity. This means that we can push more flow from s to t, and therefore we have found an augmenting path! However, this is a contradiction, since we have already computed a max flow on the graph. Hence, it is impossible for source vertex s and sink vertex t to be connected, and they must be in different sets.

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

Again we prove this by contradiction. Suppose that there is a vertex u in S and a vertex v in T, such that edge (u,v) in the residual network has flow less than capacity. By our algorithm above, this edge will be traversed, and vertex v should be in set S. This is a contradiction. Therefore, such an edge must have flow == capacity.

假设情况并非如此，并且有一些（u，v） code>将集合 S 中的顶点 u 连接到顶点 v T 中的c $ c>。我们可以将其分为两种情况：

Suppose that this is not the case, and there is some edge (u,v) that connects vertex u in set S to vertex v in set T. We can separate this into 2 cases:

1. 流经边缘（u，v）小于其容量。但这会导致顶点 v 成为集合 S 的一部分，因此这种情况是不可能的。


2. 通过边缘（u，v）的流量等于其容量。这是不可能的，因为边缘（u，v）将被视为边缘集 C 的一部分。

1. Flow through edge (u,v) is less than its capacity. But we know this will cause vertex v to be part of set S, so this case is impossible.
2. Flow through edge (u,v) is equal to its capacity. This is impossible since edge (u,v) will be considered as part of the edge set C.

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

Hence both cases are impossible, and we see that removing the edges in C from the original graph G will indeed result in a situation where there is no path from S to T.

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

The explanation on the Topcoder tutorial may not be obvious on first reading and the following is an educated guess on my part and may be incorrect.

假设存在一些边（x，y）（其中 x 属于顶点集 T 和 y 属于顶点集 S ），这样通过（x，y）的流量大于0。为方便起见，我们将e以 f 的形式流过（x，y）。这意味着在残留网络上，必须存在容量为 f 的后边缘（y，x）。 code>，流 0 。由于顶点 y 是集合 S 的一部分，因此后缘（y，x）的流量为 0 ，容量为 f> 0 ，我们的算法将遍历边缘（y，x）并放置顶点 x 作为顶点集 S 的一部分。但是，我们知道顶点 x 是顶点集 T 的一部分，因此这是一个矛盾。因此，从 T 到 S 的所有边必须具有0的流。

Suppose that there exists some edge (x,y) (where x belongs to vertex set T and y belongs to vertex set S), such that the flow through (x,y) is greater than 0. For convenience, we denote the flow through (x,y) as f. This means that on the residual network, there must exist a backward edge (y,x) with capacity f and flow 0. Since vertex y is part of set S, the backward edge (y,x) has flow 0 with capacity f > 0, our algorithm will traverse the edge (y,x) and place vertex x as part of vertex set S. However, we know that vertex x is part of vertex set T, and hence this is a contradiction. As such, all edges from T to S must have a flow of 0.

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

With these 4 facts, along with the Max-flow min-cut theorem, we can conclude that:

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

1. The max flow must be less than or equal to the capacity of any cut. By Fact 3, C is a cut of the graph, so the max flow must be less than or equal to the capacity of cut C.

事实4使我们可以得出结论：从 T 到 S 。这与事实2一起意味着流完全由从 S 到 T 的转发流组成。特别是，所有前向流量都必须来自削减的 C 。该流量值恰好是最大流量。这样，根据最大流最小割定理，我们知道 C 必须是最小割。

Fact 4 allows us to conclude that there is no "back flow" from T to S. This along with Fact 2 means that the flow consists entirely of "forward flow" from S to T. In particular, all the forward flow must result from the cut C. This flow value happens to be the max flow. As such, by the Max-flow min-cut theorem, we know that C must be a minimum cut.

这篇关于在最小切割中找到所有边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！