最大流Min-cut算法

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

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

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

假设该系统中的灰色管道具有比绿色管更大的容量，使得它是绿色网络限制了每秒系统的水量的容量。另外，假设所有绿色管都具有与彼此相同的容量。

显示答案

网络可以被切断在5个削减:

如何知道在哪里切割，以及需要五刀切割的证明:

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

1）找到水流以满体流过的管段。沿着每条水流所采取的路径的某个地方，将存在至少一个这样的管（否则，系统并不是完全使用的）。

2）一旦找到了这样的管段，就会挤压它。如果挤压它关闭会降低系统的容量，因为水无法找到另一种方式来实现，然后切割它。同样，沿着路径的某个地方每条水流需要，将存在至少一个这样的管段，否则，系统并不是完全使用的。

随着每次切割，系统的容量会逐渐减小，直到最后减少到0。

如何知道网络的“MAX-FLUS”的插图使我们能够证明网络的“MIN-CUT”是最小的：

在上面中间的图片中，你可以看到一个软管系统在满负荷使用的例子。每一条黑色的线都代表一股水流完全充满了它所经过的管道。在这张图中，系统中绘制了尽可能多的不同路径。不同的路径可以共享顶点，但不能共享边。在这些限制条件下，可以绘制的最大路径数是“最大流”这个网络。在此示例中，网络的最大流量为五个（单个绿色管的容量五倍）。

最后一张图展示了沿着一条“切割路径”切割每一条路径将如何切断网络。必须削减五次，否则至少会有一条未受影响的河流。换句话说，能够通过系统找到用于流的五个不同的水道，证明了至少五个切断系统来切断系统。因此，五也是“min-cut”网络。上面解释的水推动技术将始终允许您识别一组段，以便在一侧的“源”和另一侧的“源”上完全悬挂网络。

所有网络，无论是携带数据还是水，都相同的方式运行。网络希望将某些类型的对象（数据或水）从源从源到接收器获取。可以通过网络传递的对象的量受到网络的不相交组之间的最小连接的限制。即使这个网络中的其他边缘具有更大的容量，这些能力也不会用于最丰富。

在下面的例子中，你可以把这些网络想象成水管网络。每支箭只能放出3加仑的水。因此，网络受到潜在流量最低的分区的限制。

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

网络示例1

显示答案

答案是3.底部三个边缘可以通过其中三个，真实。然而，这里的限制因素是顶部边缘，可以一次只能通过3。这是MAX-FLOW MIN-CUT后面的直觉。最低切割将是限制因素。

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

相同的网络分成不相交的集合

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

网络示例2.

显示答案

答案仍然是3！限制因子现在在网络的底部，但权重仍然是相同的，因此最大流量仍然是3.由屏障分区的相同网络，示出了底部边缘限制了网络的流程。

同一个网络，分区的

让我们看看另一个水网，它的边缘有不同的能力。

水流网络

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

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

显示答案

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

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

从这里，只有4加仑的水能从外缘流下来。然而，每条边都有另一条边，容量为3。4加仑加3加仑比到达每个节点的6加仑多，所以我们可以让所有的水通过这一层。

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

重要的是要明白并不是每条边都能满载水。从容量的角度来看，这是网络的一个示例。现在，每条边都显示出它目前承载了多少水超过它的总容量。

水流量网络容量

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

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

一个减少是网络的一个分区， $G$分为两个脱节的顶点集。这些集合称为 $年代$和 $T$． $年代$这个集合包括源和吗 $T$是包括水槽的集合。唯一的规则是源和宿区不能在同一组中。削减有两个重要的属性。第一个是割集，这是一组开始的边 $年代$和结束在 $T$．第二是能力，这是边缘中的重量的总和割集．查看下面的图形以获得这些属性的可视化描述。

削减S，容量为7

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

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

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

引理1:
对于任何流 $f$和任何削减 $(S, T)$在网络上，它保持了这一点 $f \leq \text{capacity}(S, T)$．这是有道理的，因为对于那种流量的空间不可能有更多的流动（或者，对于比管子可以拟合的水比水更多）。

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

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

证明:
从任何流程开始 $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)$必须是最大的，否则我们就会有一个增加的路径。还有，流动 $（v，u）$必须出于零以出于同样的原因。所以， $\text{flow}(u, v) = \text{capacity}(u, v)$对于所有边 $u$在 $V$和 $v$在 $V c ^$,所以 $\文本{flow}（v，v ^ {c}）= \ text {capacity}（v，v ^ {c}）。$然后，根据推论2， $f ^ {*} = \ text {容量}（s，t）^ {*}。$

网络可以看起来与本wiki中显示的基本网络非常不同。然而，最大流最小割定理仍然可以解决这些问题。如果网络有多个来源，比如下面这个(每个来源顶点都被标记为S)呢?

具有多个来源的流量网络

毫无疑问，只需一个源就可以创建一个新的网络。这个源与所有原始源相连，而来自新源的每条边的容量都是无限的。同样的过程也可以用于处理多个汇聚顶点。

源顶点合并的流网络

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