1.网络流：流&网络&切

1.网络流量问题（Flow）：

给定一个指定的有向图，其中有两个特殊点源S()和汇T()，并且每条边都有指定的容量()，求满足条件()的从S到T的最大流量。

流a G 带有一组S 和T，并且对于每条边都有一个()，然后要求找到可以从S 到T 的流 边 。

这是一个简单的解释

（以下基本避免形式化证明，基本采用这种描述）

比如你家是一个供水厂（有需要的同学可以把供水厂看成银行或者下面类似的东西）。

然后还有很多水管连接在水厂和你的房子之间。水管有不同的规格，有的容量大，有的容量小。

然后要求水厂打开闸门放水。您家的最大供水流量是多少？

如果自来水厂停水了，你家的流量就是0，这肯定不是最大流量。

但是你给水厂付了100万美元。自来水厂尽力打开水管，但你家的流量却始终保持不变。此时，已达到最大流量。

-------------------------------------------------- -------------------------------------------------- ----------

2. 三个基本属性：

如果C表示每条边的容量，F表示每条边的流量

一个明显的事实是F小于等于C，否则水管会爆裂。

这是网络流的第一个属性容量极限（ ）：F ≤ C

再考虑一下，任何节点的流入量总是等于流出量，否则就会积水（有爆炸的危险……）或者会无缘无故地释放更多的水（地下水涌出？）

这就是流量守恒（Flow）的第二个性质：ΣF=ΣF

当然，源和汇不需要满足流量守恒定律。我们不需要关心自来水厂的水是来自河流还是河水。

（插播：节约用水，人人有责！）

最后一个不太明显的属性是斜对称性 (Skew)：F = - F

这对于一个完整的网络流理论来说实际上是必不可少的，就像中学物理中用正数和负数来定义一维位移一样。

如果起点100米到终点100米的位移为100m，则终点到起点的位移为-100m

类似地，如果x流向y，F的流将流向x，y将流向x - F的流。

-------------------------------------------------- -------------------------------------------------- ----------

3、容量网络&流量网络&残差网络：

网络是具有源和汇的有向图。边权重的含义是什么？

容量网络是关于容量的网络，基本上不会改变（很少有问题需要改变）

交通网络是关于交通的网络。在解决问题的过程中

通常不断变化但始终满足上述三个属性

调整到最后就是最大流量网络，也可以得到最大流量值。

残差网络经常总结容量网络，流量网络最常用

剩余网络=容量网络-流量网络

该方程始终成立，当流量值为负时，剩余值甚至可以大于容量值。

为什么流量值为负值？如果有积极的一面，就一定有消极的一面。记住倾斜对称性！

-------------------------------------------------- -------------------------------------------------- ----------

4. 切割及切割组：

无向图的割集：C[A,B] 是 A 和 B 之间的边的完整集合，它将图 G 分为两个点集 A 和 B。

一组a​​、if（或“剪切”）、the（即a）。

网络的割集：C[S,T]是从S到T的边的完整集合，它将网络G分为两部分：s和t。点集S属于s，T属于t。

带权图的割是割集中边或有向边的权重之和。

a , G=(V,E) 和 V 的 a 分成两个集合 A 和 B，G 与 A 和 B 的割为 cut(A,B)=sum_(i in A,j in B)W( i,j), W(i,j) 表示边 i 和 j。切割的 是切割的总和。

用简单的方式来理解它：

切断就像恐怖分子切断了你家和自来水厂之间的一些水管网。

那么无论水厂放出多少水，水都会从水管破裂处流出，你的家将无法供水。

（插播：节约用水，人人有责！）

削减的规模应该是恐怖分子应该关心的事情。毕竟，细管子更容易切割。

最小的花需要最小的努力

=================================================== ==================================

2. 计算最大流量的基本算法

那么如何求一个网络的最大流量呢？

下面是最简单的算法： -Karp算法，最短路径增广算法，简称EK算法

EK算法基于一个基本方法：福特法，即增广路径法或简称FF法。

增广路径方法是许多网络流算法的基础，一般在残差网络中实现。

其思想是找到一条从源到汇每次都能增加流量的路径，调整流量值和残差网络，直到没有增加的路径为止。

FF方法的基础是增广路径定理（Path）：当且仅当残差网络中不存在增广路径时网络达到最大流

如果省略证明，这个定理应该是可以接受的。

EK算法就是不断寻找最短路径。方法是寻找每次边数最少的增广，即最短路径增广。

这就引出了三个问题：

-------------------------------------------------- -------------------------------------------------- ----------

1.我们最多需要增广多少次？

可以证明最多O(VE)次的增强可以达到最大流量。证明稍微

2.如何找到增光路？

首先要明确什么是增光路。增光路是一条从s到t的路。路径上每条边的剩余容量均为正。

将剩余容量为正的边设置为可行边，然后我们可以使用简单的BFS来得到边数最少的增广路径。

3、如何增强？

BFS获得增广道路后，这条增广路径能够增广的流量值由该路径上的最小剩余通行能力边来确定。

将这个最小剩余容量值与最大流量值 Flow 相加，并减去路径上每条边的剩余容量值。

为什么要在最终路径上添加每条边的反向边剩余容量值？下面将详细说明。

-------------------------------------------------- -------------------------------------------------- ----------

这样每次增广的复杂度就是O(E)。 EK算法的总复杂度为O(VE^2)

事实上，大多数网络只有很少的增强，而 EK 算法可以处理大多数问题。

平均而言，增强路径算法非常快。

增光路算法就像自来水公司不断地将水一一抽入自来水管网。

上面还剩下一个反向边的问题：为什么要加上增广路径上每条边的反向边的剩余容量值呢？

因为斜对称！因为残差网络=容量网络-流量网络

无需改变容量网络

由于增光就像给增光路增加了一条人流路径，所有侧面的交通量都增加了

交通网络中路径上侧的流量加上反向侧的流量减去

相应的残差网络发生相反的变化。

这样我们就完成了EK算法的具体实现。我们可以使用邻接表来存储图，或者使用邻接矩阵来存储图。

邻接表存储图。由于流量存在于边和反向边上，为了方便获得反向边图，将一对彼此相对的边构建在一起。

代码很简单，最好自己实现一下

EK

我们来看一个增广路径算法的具体例子。

=================================================== ==================================

3. 最大流和最小割定理

下面介绍网络流理论中最重要的定理之一。

最大流与最小割定理（Flow, Cut）：网络的最大流等于最小割

G 中的流 v_i 和 v_j 是 中 v_i 和 v_j 的 G 的集合。

具体证明分为三个部分

1.任意流量小于或等于任意割

这很容易理解。自来水公司会随机提供一些水到你家形成水流。

恐怖分子随手砍了几刀就砍了

由于容量限制，每根切割水管流出的水量小于管道的容量。

每根被切断的水管的水原本是流向你家的。现在它流到外面，总流量仍然等于原来的流量。

管道总容量被切断，因此流量小于或等于切断

由于上述流和割是任意构造的，任何流都小于任何割。

2.构造一个等于割的流

当达到最大流量时，根据增光路定理

残差网络中没有从s到t的路径，否则可以继续增长。

让我们将s可以到达的点的集合设置为S，将不能到达的点的集合设置为T。

构造割集 C[S,T]。从S到T的边必须是全流的，否则可以继续增长。

这些全流量边缘上的流量之和就是当前流量，即最大流量。

将这些全流边作为割，构建等于最大流的割。

3. 最大流量等于最小割量

令相等的流量和割量分别为 Fm 和 Cm。

那么因为任何流量都小于或等于任何割

任意F≤Fm=Cm≤任意C

定理解释完成