最大流Min-cut算法

的最大流min-cut定理是一个网络流定理。这个定理指出，从一个给定源到一个给定汇聚的任何网络的最大流量恰好是边权值的总和，如果去掉这些边权值，将完全断开源和汇聚的连接。换句话说，对于任何网络图和选定的源和汇聚节点，源到汇聚的最大流量=源和汇聚分离所需的最小切割量。心流适用于任何事物。例如，它可能意味着流经网络管道的水量。或者，它可能意味着可以通过像互联网这样的计算机网络传输的数据量。

最大流量最小切割具有多种应用。在计算机科学中，网络很大程度上依赖于这种算法。网络可靠性、可用性和连通性使用最大流量最小削减。在数学中，图的匹配(如二部匹配)使用相同的算法。在技术要求较低的领域，该算法也可用于调度。例如，航空公司利用这一点来决定何时允许飞机离开机场，以最大限度地提高航班的“流量”。

为了不让水从消防栓流到水桶，最少需要切断多少根绿管?

假设这个系统中的灰色管道比绿色管道的容量大得多，所以绿色网络的容量限制了每秒通过系统的水量。另外，假设所有的绿管都具有相同的容量。

显示答案

网络可分为5路切断:

如何知道哪里需要削减，并证明需要削减五项:

如果这个系统是真的，那么解决这个难题的一个快速方法就是让水从消防栓喷射到绿色软管系统。一旦水以系统能够管理的最高容量流经网络，观察水是如何流经系统的，并重复遵循这两个步骤，直到网络完全切断:

1)找到一个管段，水是流动的全部能力。在每条水流经过的路径上，至少会有一根这样的管道(否则，系统就不会真正满负荷运转)。

2)一旦你发现了这样的管段，试着挤压它。如果因为水找不到其他途径通过而导致系统容量下降，那就切断它。同样，在每条水流经过的路径的某个地方，至少会有一个这样的管段，否则，系统就不能真正满负荷使用。

每削减一次，系统的容量就会减少，直到最后减少到0。

一个例子表明，知道网络的“最大流量”可以让我们证明网络的“最小切割”实际上是最小的:

在上面的中间图片中，你可以看到一个例子，如何使用软管系统可能满负荷运转。每条黑线都代表一股水流，它完全充满了流经的管道。在这幅图中，在整个系统中绘制了尽可能多的不同路径。不同的路径可以共享顶点，但不能共享边。在这些限制条件下，可以绘制的最大路径数是“最大流”这个网络。在这个例子中，网络的最大流量是5(5倍于单个绿管的容量)。

最后一张图说明了如何沿着单一的“切割路径”切断这些路径中的每一条，将切断网络。需要砍五刀，否则至少会有一条不受影响的水流。换句话说，能够找到五个不同的路径，让水流经系统证明，至少需要五个切割来切断系统。因此，五也是“min-cut”的网络。上面解释的推水技术将总是允许你确定一组段，以“源”在一边，“汇”在另一边完全切断网络。

所有的网络，无论是传输数据还是供水，运作方式都差不多。网络希望从源获取某种类型的对象(数据或水)。可通过网络的该对象的数量受到网络不相交集合之间的最小连接的限制。即使网络中其他边缘的容量更大，这些容量也不会被充分利用。

在下面的例子中，你可以把这些网络想象成水管网络。每只箭只能允许3加仑的水通过。因此，网络受限于具有最低势能流的分区。

1. $＼$请看下面的图表。它是一个有四条边的网络。源在网络的顶部，而汇聚在网络的下方。每条边的最大流量(或重量)为3。在任何给定时间，有多少流量可以通过这个网络?

网络示例1

显示答案

答案是3。下面三条边可以通过这三条边中的9，为真。然而，这里的限制因素是上边缘，它一次只能通过3条。这就是最大流量最小切割背后的直觉。最低削减将是限制因素。

如下图所示，通过将网络分割成不相交的集合，我们可以看到其中一个集合显然是限制因素，即上边缘。上面一套最大重量只有3，下面一套最大重量是9。上半部分限制了网络的流量。

同一个网络分裂成不相交的集合

2. $＼$这个网络的最大流量是多少?

网络示例2

显示答案

答案仍然是3!限制因子现在在网络的底部，但是权值还是一样的，所以最大流量还是3。同样的网络，用屏障分割，显示底部边缘限制了网络的流量。

相同的网络，分区

让我们看看另一个水网它有不同容量的边缘。

水流网络

在这张图中，每条边代表了在任何给定时间内可以通过它的水量(单位为加仑)。

1. $＼$这个网络的最大流量是多少?

显示答案

答案是10加仑。让我们从源头开始，逐层分析整个过程:

1) 6加仑的水可以从源头传递到下一层的两个顶点。到目前为止一共是12加仑。

2)从这里开始，只有4加仑的水可以通过外缘。然而，每条边都有一条容量为3的边。4加仑加3加仑大于到达每个节点的6加仑，所以我们可以让所有的水通过这一层。

3)从这一层到水槽的唯一路径是通过一个容量为5的边缘。这意味着每个顶点只能排出5加仑的水，总共是10加仑。这就是网络的最大流量。

重要的是要明白，不是每个边缘都将以最大容量携带水。这是从容量角度来看网络的一个例子。现在，每条边都显示出它目前携带的水量超过了它的总容量。

水流量网络容量

这个算法有几个关键的定义。首先，网络本身是一个有向加权图。也就是说，它是由一组由边连接的顶点组成的。这些边只在一个方向流动(因为图是有向的)，而且每条边也有它能处理的最大流量(因为图是加权的)。

在这个图中有两个特殊的顶点。的源是所有流动的来源。所有接触源的边都必须离开源。这是水槽，所有的流都流向这个顶点。类似地，所有接触水槽的边都必须进入水槽。

一个减少是对网络的划分， $G$，分解成两个不相交的顶点集合。这些集合被称为 $年代$而且 $T$． $年代$集合是否包含源和 $T$是包含接收器的集合。唯一的规则是源和接收器不能在同一个集合中。切割有两个重要的特性。首先是割集，也就是从这里开始的边的集合 $年代$和结束在 $T$．第二个是能力中的边的权值之和割集．查看下面的图表以获得这些属性的可视化描述。

以7的容量削减S

在这张图中，被圈起来的两个顶点在集合中 $年代$，其余的都加入了 $T$． $年代$在它的割集中有三条边，它们的综合权重为7，也就是这个割集的容量。然而，最大流量最小切割的目标是找到与最低能力。

有许多具体的算法在实践中实现这个定理。最著名的算法是Ford-Fulkerson算法1956年，两位科学家发现了最大流量最小切割定理，并以此命名。

首先，有一些重要的初始逻辑步骤来证明任何网络的最大流量等于该网络的最小割。

引理1:
对于任何流 $f$和任何削减 $(S, T)$在网络中，它持有这个 $f \leq \text{capacity}(S, T)$．这是有道理的，因为不可能有更多的流动超过流动的空间(或者，有更多的水超过管道所能容纳的)。

推论2:
根据引理1，我们有了明确的下一步。对于最大流量 $f ^ {*}$最小切割 $(S, T) ^ {*}$,我们有 $f^{*} \leq \text{capacity}\大((S, T)^{*}\大)。$

这两个数学表述给出了最大流量的上界。

证明:
从任何流程开始 $f$．这是可能的，因为零流量是可能的(网络中没有流量)。然后重复下面的剩余图创建过程，直到没有剩余的增广路径。

定义增广路径 $p_a$作为从网络的源到汇聚的路径，可以增加更多的流量(从而增加网络的总流量)。

在这个过程的每一步，我们都想创建一个残差图 $G_f$．要做到这一点，首先要找到一个增广路径 $p_a$有给定的最小容量 $c_p$．也就是说, $c_p$是路径上所有边的最小容量吗 $p_a$．

对于每条有端点的边 $(u, v)$在 $p_a$，增加流量从 $u$来 $v$通过 $c_p$减少来自 $v$来 $u$通过 $c_p$．这可能需要在向后方向上创建一条新边。该过程不改变边缘的容量约束，保持了流的非负性。同时，这也增加了从源到汇的流量 $c_p$．这就是剩余图的创建方法。

现在，重要的是要注意我们的新流程 $F ^{*} = F + c_p$不再包含递增路径 $c_p$．这是因为增加我们流量的过程 $c_p$要么给其中一个前进边一个最大容量，要么给其中一个后退边一个零流量。

这个过程会重复，直到没有扩展路径存在为止。一旦发生这种情况，将所有从源可达的顶点表示为 $V$以及所有不能从源到达的顶点 $V c ^$．很简单，源在 $V$水槽进水了 $V c ^$．重要的是，水槽是不在 $V$因为没有递增路径，因此也就没有从源到汇聚的路径。

考虑一对顶点， $u$而且 $v$,在那里 $u$是在 $V$而且 $v$是在 $V c ^$．的流动 $(u, v)$必须是最大化的，否则我们就会得到一条增广路径。然后，流动 $(u, v)$因为同样的原因，一定是零。因此, $\text{flow}(u, v) = \text{capacity}(u, v)$对于所有具有 $u$在 $V$而且 $v$在 $V c ^$,所以 ${流}\文本(V, V ^ {c}) ={能力}\文本(V, V ^ {c})。$那么，通过推论2， $f^{*} = \text{capacity}(S, T)^{*}。$

网络可能与本维基所展示的基本网络有很大的不同。然而，最大流量最小切割定理仍然可以处理它们。那么像下面这样有多个源(每个源顶点标记为S)的网络呢?

多源流网络

只需一个来源就可以创建一个新的网络，这一点都不麻烦。这个源连接到原始版本的所有源，来自新源的每条边的容量都是无穷大的。同样的过程可以用于处理多个汇聚顶点。

源顶点合并的流量网络

这个微小的变化不会影响网络的流势，因为这些只是增加了具有无限容量的边，它们不会造成任何瓶颈。这使得我们仍然可以运行最大流量最小切割定理。