12.28网络流，残留网络，增广路，最大流最小割定理

网络流 概念

是指在一个每条边都有容量的有向图分配流，使一条边的流量不会超过它的容量。通常在运筹学中，有向图称为网络。顶点称为节点而边称为弧。一道流必须匹配一个结点的进出的流量相同的限制，除非这是一个源点──有较多向外的流，或是一个汇点──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

算法案例引入 :
然后自来水厂和你家之间修了很多条水管子接在一起 水管子规格不一 有的容量大 有的容量小
然后问自来水厂开闸放水 你家收到水的最大流量是多少

明确概念 :
容量：每条边都有一个容量(水管的最大水流容量)
源点：出发点(水厂)。
汇点：结束点(废水站)。
流：一个合法解称作一个流，也就是一条可以从源点到汇点的一条合法路径。
流量：每条边各自被经过的次数称作其流量，最终收集的总数为整个流的流量。

最大流

a-d-g后，a是源点，流量是无穷的；d的那个节点，出了3个，入的是7个，所以最多还能出4个；g的那个节点，出了3个，最大容量是4，所以最多还能出1个

?

当我们率先计算b-f-g这条边的时候，我们贪心的把整条路都填满，导致g的容量全部被来自b的量占据了。这代表着a无法再利用这条边，只能向下从e流出。

甚至我们可以想象，在复杂的网络中，一个节点的流出的边很可能全部被其他流占用，导致流向该节点的“货物”全部失效了。如果这部分货物占据了总流量的很大部分，那么结果就很有可能出现错误。

为了避免这个现象Ford-Fulkerson算法建立了反向边，即“反悔”机制。

算法沿着路径反向建立额外的路，这条额外的路的容量就等于整条路的流量。

此时，我们完成了第一步，即b-f-g：4

然后我们继续

• b-c-h：2
• a-d-f’-c-h：2（这里用的是建立的反向边）
• a-e-h：2

最大流4+2+2+2=10。结果正确。

在这里你能看到“反悔”机制是如何作用的，他将多余的流量回退。本来正确的路线是b-f-g：1，结果我们因为顺序的不同导致b-f-g率先占据更多的容量，而反向边的建立使得我们有机会将多余的3份流量回退回去，产生正确的结果。

反向边建立的必要性

反向边的容量就是输入进去的流容量，允许反悔退回来

不是反悔而是借用

?FF算法是一种贪心算法，它总是尽可能沾满一条边的容量。比如从a-c这条路走，它会送出去5的流量，而非3或4。这个概念其实相当重要。

正确计算顺序是这样的：

• a-c：5
• a-e-d：5
• b-d：2

但顺序打乱一下，同时建立反向边：

a-e-d：8
a-c：2
b-e’-c：2（用了反向边）
结果正确，但是这个时候我们再以“反悔”的视角来看，按照刚才的顺序，a-e-d这条路应该是5，应该反悔3个流才能得到正确的答案，但是这里我们仅仅反悔了两个流，也就是说，现在成了这个样子：

a-e-d：8-2=6
a-c：2+2=4
b-d：0+2=2
a的分配明显不符合贪心的思想。

但关键就在于这一点，即便不符合贪心，即便没有完全的“反悔”，算法依旧健壮，依旧完美的运作，其中所蕴含的数学究竟是什么？是什么保证了它如此完美的运作？

为了使例子更具有普遍性，我们讲每条边的容量值用任意值代替。

a先走c：这个时候我们先让a优先占用c边，有两种情况。

a<c：这个时候不需要建立反向边，因为a不走e，a的流量全部被c给拿走了。
a>c：当a大于c时，那么a剩余的流量会走e同时建立反向边。但是这个时候反向边也是无用的，试想，当b流通过反向边来到c时，发现c的容量早已经被a占满了。所以反向边的建立起不到任何作用，b还是老老实实走d才行。
可以看到，a先走c是符合我们计算顺序的，这个时候无论建不建立反向边都是不影响结果的。

a先走e：两种情况

a<e：这个时候建立反向边，但是往下b和e汇合的时候还分两种情况
b+e<d：这说明d容量足够大，足以容纳a和b的总容量，b这个时候也有可能不走反向边。
如果b不走反向边，正常运作
如果b走反向边，那么b就会和反向边的容量判断大小，之后剩余容量肯定能走d，通过反向边的流量则借用原来a需要走的c边。
b+e>d：这个时候b的剩余容量就必须要走反向边，借用a原来走的c边。
a>e：如果a有剩余流量，它会讲剩余流量走c边，同时建立反向边让b边有机会借用c自己的c边，防止b被阻塞。
好吧，我承认上述的分类有些乱糟糟的，确实这方面也不太好说，所以我下面以一种方便的形式展示一下 “借用” 的意思。
?

?

（源点可以出任意数量的水，但是每个节点不一定能接受并输出，因为有输出容量限制，所以就是调控路线，使从源点输出的水，到汇点时，所能达到的流量最大，就是最大流问题）

最大流问题的目标是在一个给定的有向图中找到一条从源点到汇点的路径，使得路径上的流量总和最大。

在一个有向图中，最大流问题中每条边都有一个容量限制，表示该边能够承载的最大流量。源点代表流量的起点，汇点代表流量的终点，其他节点都是中间节点，用来连接源点和汇点的路径。每条路径的流量取决于路径上容量最小的边，也就是瓶颈边的容量

割不同，则割容量不同

残留网络和增广路径概念

残留网络：
由原始流网络和当前的流组成。对于每条边（u，v），它的残量r(u，v)是指在原始流网络中该边的容量减去当前流的流量。即：（就是没流的那部分，还没到限制的剩余流量，可以扩加的流量）
r(u，v) = c(u，v) - f(u，v)
其中，c(u，v)是边（u，v）的容量，f(u，v)是在该边上已经流过的流量。
同时，残留网络中还包含了反向边（v，u）用于指示是否可以反向增加流量，因此对于每条边（u，v），在残留网络中可以对应两条边：(u，v，r(u，v))和(v，u，f(u,v))。

在残留网络中，每条原始边会对应生成两条边。这是因为在最大流问题中，我们需要考虑正向流和反向流。

正向流是指从源节点到汇节点的流量传输，而反向流则是指从汇节点到源节点的逆向流量传输。

为了能够考虑到反向流，在求解最大流问题时，我们会将原始网络中的每条边拆分成两条边，分别对应正向流和反向流。

具体来说，假设在原始网络中存在一条边从节点A到节点B，容量为C。在残留网络中，会生成两条边，一条是从节点A到节点B，表示正向流；另一条是从节点B到节点A，表示反向流。

通过这样的拆分，我们可以在残留网络中同时考虑正向流和反向流的影响。当我们在残留网络中搜索增广路径时，会优先选择有残留容量的正向边，或者去取消反向边上的流量，从而更新网络中的流量分布。

之所以要指示是否可以反向增加流量，是因为后续节点的流出与流入也有限制，最大不能超过流入它的部分，即源点与汇点互换，同样也可以流通，那么就是流入与流出的方向互换

残留网络是在解决最大流问题时使用的一个概念，它反映了在当前流网络中，每条边还能够容纳的额外流量。

在一个网络中，每条边都有一个容量值，表示该边可以传输的最大流量。当流经某条边的流量小于其容量时，该边上存在残留容量，表示该边仍有能力传输更多的流量。

残留网络是通过根据当前的流量和容量计算而得。对于每条边，残留容量可以通过其容量减去当前流量来得到。如果残留容量大于零，则表示该边上仍有可用的流量传输。

利用残留网络可以确定增广路径，即从源节点到汇节点的一条路径，沿该路径上的边存在足够的残留容量可供进一步增加流量。通过不断寻找增广路径并更新流量，最终可以求解出最大流问题。

在求解最大流问题的算法中，使用残留网络来指导增广路径的选择以及更新流量和残留容量。

增广路径：
指在残留网络中从源点s到汇点t存在一条路径，沿着这条路径可以增加流量并且不超过路径上的最小残量。
具体来说，假设当前的残留网络是G’=(V, E’)，其中E’包括正向边和反向边，容量为r，源点为s，汇点为t。增广路径是一条从s到t的简单路径，即不重复经过任何节点的路径。这条路径的最小残量是路径上所有正向边和反向边的残量的最小值，即：
min{r(u,v) | (u,v)是增广路径上的边}
在增广路径上，我们可以将最小残量加到当前流上，从而增加总的流量。同时，我们需要在残留网络中更新增广路径上的边的残量，即减少正向边的残量或增加反向边的残量。
?

证明：残留网络和其流网络之和仍是可行流
具体来说，假设当前的流网络是G=(V, E)，其对应的残留网络是G’=(V, E’)，当前流为f，残留网络的边容量为r，那么将G和G’相加得到的新网络G’‘=(V, E’‘)，其边容量为：
c’‘(u,v) = r(u,v) + f(u,v)，若(u,v)∈E’
c’'(u,v) = c(u,v) - f(u,v)，否则

容易证明，G’‘中的任何一个流f’‘都是一个可行流。因为对于任何节点u∈V，其入流量等于出流量，即：
∑f’'(u,v) = ∑f(u,v) + ∑r(u,v) - ∑f(v,u) = ∑c(u,v) - ∑f(u,v) + ∑f(u,v) = ∑c(u,v)

因此，G’‘中的任何一个流都满足容量限制。另外，由于G’是由G和当前流f推导出来的，因此G’'中的任何一个流都满足流守恒条件。

-----》残留网络中没有可行流，原网络是最大流
?

算法分析 :

容量限制：每条边的流量不超过其容量(水管会爆的)。
流量平衡：对于除源点和汇点以外的点来说，其流入量一定等于流出量。
现在，先简化一下这个图，来解决这个问题。
x/y表示总流量为y，已经流了x.

最大流是2

容量为0表示两个节点间没有边

定义一跳变得残量为：容量 - 已流过的流量。
反向边的流量值=正向流过的总流量，也就是说正向流过多少，反向可以流回多少。

最大流最小割定理 :

最大流最小割定理提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。
这个定理说明，当网络达到最大流时，会有一个割集，这个割集中的所有边都达到饱和状态。
这等价于在网络中再也找不到一个从s到t的增广路径。
因为只要能找到一条增广路径，这条增广路径肯定要经过最小割集中的一条边，否则这个割集就不能称之为割集了。
既然这个割集中所有的边都饱和了，因此也就不会存在这样的增广路径了。
这个定理的意义在于给我们指明了方向：
任何算法，只要最后能达到“再也找不到一条增广路径”，就可以说明这个算法最后达到了最大流。

小结 :
总结一下上面求最大流的步骤：
1.在图上找到一条从源点到汇点的路径(称为‘增广路’)。
2.去增广路上的残量最小值v。(也就是流过的路径中流量最小的那一个)
3.将答案加上v。
4,.将增广路上所有边的残量减去v，反向边的残量加上v。
重复上边4个步骤直到找不到增光路为止

割集

割集是在集合中将其分成两个不相交的子集的一种划分方式。这种分割可以通过选择一个或多个元素，将集合中的元素分成两个部分，并且每个元素要么属于第一个子集，要么属于第二个子集。

举个例子，考虑集合A = {1, 2, 3, 4, 5}。我们可以选择将A划分成两个不相交的子集B和C。我们选择将奇数放入B子集，偶数放入C子集，即B = {1, 3, 5}和C = {2, 4}。在这个例子中，B和C就是A的一个割集。注意，这个划分方式满足两个条件：1）B和C是不相交的子集，即B∩C = ?；2）B和C的并集等于A，即B∪C = A。

割集可以用于多种应用，比如图论中的最小割问题，其中需要找到一种割集方式，使得切割图中的边的权重之和最小。

求解最大流问题通常使用网络流算法，其中最著名的算法是Ford-Fulkerson算法。

Ford-Fulkerson算法的基本思想是不断在残余网络中寻找增广路径，并更新流量，直到无法找到增广路径为止。以下是Ford-Fulkerson算法的基本步骤：

1. 初始化网络流：将每条边的流量设为0。

2. 在残余网络中寻找增广路径：可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来寻找增广路径。增广路径是一条从源节点到汇节点的路径，该路径上的边的残余容量大于0。

3. 更新流量：找到增广路径后，将路径上容量最小的边的容量作为增加的流量值，更新路径上每条边的流量。

4. 更新残余网络：根据已更新的流量，计算每条边的残余容量，更新残余网络。

5. 重复步骤2-4，直到无法找到增广路径为止。

最终，最大流等于从源节点流出的总流量。在Ford-Fulkerson算法中，可以使用不同的方法来选择增广路径，例如Edmonds-Karp算法使用BFS来寻找最短增广路径，具有较好的时间复杂度。

除了Ford-Fulkerson算法，还有其他网络流算法，如Dinic算法和Push-Relabel算法，它们在实现上有所不同，但思想都基于不断寻找增广路径来增加流量。