20220101-《算法导论》第26章-最大流
学习笔记：《算法导论》第26章-最大流
0. 背景
- 可以将有向图理解成一个”流网络“，用来回答有关物流方面的问题。
- 设想某物质从产生它的源点经过一个系统，流向消耗该物资的过程。源点以固定速度产生该物质，而汇点则用同样的速度消耗该物质。从直观上看，系统中任何一点的物质的”流“为该物质在系统中运行的速度；
- 应用场景：模型化流经管道的液体、通过装配线的部件、电网中的电流或通讯网络传送的信息等；
1. 最大流的概念
- 流网络中的每条有向边可以被认为是传输物质的管道。
- 每个管道都有一个固定的容量，可以看作是物质能够流经该管道的最大速度。
- 流守恒（flow conservation）：物质进入某顶点的速度必须等于该顶点的速度。
- 当物质是电流时，流守恒与基尔霍夫电流定律等价；
- 最大流问题：在不违背容量限制的条件下，把物质从源点传输到汇点的最大速率是多少；
- 流网络：
- $G=(V, E)$是一个有向图，其中每条边$(u, v) \in E$均有一非负容量$c(u, v) \geqslant 0$。如果$(u, v) \notin E$，则假定$c(u, v)=0$。
- 流：
- $G=(V, E)$是一个有向图，其容量函数为$c$。设$s$为网络的源点，$t$为汇点。$G$的流是一个实值函数$f: V \times V \rightarrow \mathbf{R}$，且满足下列三个性质：
- 容量限制：对所有$u, v \in V$，要求$f(u, v) \leqslant c(u, v)$；
- 容量守恒：对所有$u \in V-\{s, t\}$，要求$\sum_{v \in V} f(u, v)=0$；
- 反对称性：对所有$u, v \in V$，要求$f(u, v)=-f(v, u)$；
- $f(u, v)$：称为从顶点u到顶点v的流；
- 流$f$的值：$|f|=\sum_{v \in V} f(s, v)$，即从源点出发的总流；
- $G=(V, E)$是一个有向图，其容量函数为$c$。设$s$为网络的源点，$t$为汇点。$G$的流是一个实值函数$f: V \times V \rightarrow \mathbf{R}$，且满足下列三个性质：
- 最大流问题实际上是给出一个具有源点$s$和汇点$t$的流网络$G$，希望找出从$s$到$t$的最大值流；
- 对流的处理：
- 隐含求和记号：其中任何一个自变量或两个自变量可以是顶点的集合，他们所表示的值是对自变量所代表元素的所有可能情形求和。例如，如果X和Y是顶点的集合，则：$f(X, Y)=\sum_{x \in X} \sum_{y \in Y} f(x, y)$；
- 几个引理：
- 对所有$X \subseteq V, f(X, X)=0$；
- 对所有$X, Y \subseteq V, f(X, Y)=-f(Y, X)$；
- 对所有$X, Y, Z \subseteq V$，其中$X \cap Y=\varnothing$，有：
- $f(X \cup Y, Z)=f(X, Z)+f(Y, Z)$；
- $f(Z, X \cup Y)=f(Z, X)+f(Z, Y)$；
2. Ford-Fulkerson方法
Ford-Fulkerson方法依赖于三种重要思想：
- 残留网络（residual network）；
- 增广路径（augmenting path）：可以看作是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值；
- 割（cut）【用流网络的割来描述最大流的值】；
Ford-Fulkerson方法是一种迭代方法：
- 初始状态时流的值为0；
- 在每次迭代中，可以通过寻找一条”增广路径“来增加流值；
- 重复上一步骤，知道所有增广路径均被找出位置；
最大流最小割定理说明：当算法停止时，上述过程可以产生最大流；
残留网络：假设$f$为$G$中的一个流，并考察一对顶点$u, v \in V$：
- 残留容量：在不超过容量$c(u,v)$的条件下，从u到v之间可以压入的额外网络流量，就是$(u,v)$的残留容量，定义为：$c_{f}(u, v)=c(u, v)-f(u, v)$；
- 残留网络：给定一个流网络$G=(V,E)$和流$f$，由$f$压得的G的残留网络是$G_{f}=\left(V, E_{f}\right)$, $\begin{equation}
E_{f}=\left\{(u, v) \in V \times V: c_{f}(u, v)>0\right\}
\end{equation}$；
引理1：设$G=(V, E)$是源点为s、汇点为t的一个流网络，且f为G中的一个流。设$G_{f}$是由导出的G的残留网络，且$f^{‘}$为$G_{f}$中的一个流，那么定义$f+f^{‘}$是G中的一个流，其值为$\left|f+f^{\prime}\right|=|f|+\left|f^{\prime}\right|$；
增广路径：残留网络$G_{f}$中从s到t的一条简单路径；
残留容量：能够沿一条增广路径p的每条边传输的网络流的最大量为p的残留容量，定义为：
引理2：设$G=(V, E)$是一个流网络，f是G的一个流，并设p是$G_f$中的一条增广路径，定义函数$f_p$为：
则定义$f_p$为$G_f$上的一个流。
引理3：通过 $f^{\prime}=f+f_{p}$ 定义一个函数 $f^{\prime}: V \times V \rightarrow \mathbf{R}$ ，则 $f^{\prime}$ 是 $G$ 的一个流， 其值$\left|f^{\prime}\right|=|f|+\left|f_{p}\right|>|f|$；
网络的最小割：是网络中所有割中具有最小容量的割；
流网络的割：Ford-Fulkerson方法沿增广路径反复增加流，直至找出最大流时为止。
引理4：设f是源点为s，汇点为t的流网络G中的一个流。并且(S，T)是G的一个割。则通过割(S，T)的净流为$f(S,T)=|f|$。
引理5：对一个流网络G中任意流f来说，其值的上界为G的任意割的容量；
最大流最小割定理：如果f是具有源点s和汇点t的流网络G=(V,E)中的一个流，则下列条件等价：
- f是G的一个最大流；
- 残留网络$G_f$中不包含增广路径；
- 对G的某个割(S,T)，有$|f|=c(S,T)$；
Ford-Fulkerson算法：
- 在每次迭代中，找出任意增广路径$p$，并把沿$p$每条边的流$f$加上其残留容量$c_f(p)$。
Edmonds-Karp算法（EK算法）：使用bfs实现对增广路径$p$的计算；
3. 最大流的经典应用：最大二分匹配
可以和匈牙利算法进行比较。