max-flow 和 min-cut

流网络 Flow network

流网络定义为一个元组 $G=(V,E,s,t,c)$

• V：流网络中点的集合
• s：源点，没有流量输入，只有流量输出，$s\in V$
• t：汇点，没有流量输出，只有流量输入，$t\in V$
• E：流网络中边的集合
• $c(e_i)$：边的容量，$c(e_i)>=0$
  

最小割 Min-cut

割 (s-t cut) 被定义为一个点的划分 $(A,B)$，其中$s\in A$，$t\in B$。即将流网络的所有点，分成两个部分 A 和 B。
割的容量(capacity)：定义为 从 A 到 B 线段的容量之和：$cap(A,B)={\sum }_{eoutofA}c(e)$

如下图所示，A 仅包含 s，因此 $cap(A,B)=10+5+15=30$。

下图割的容量：$cap(A,B)=10+8+16=34$。

最小割(Min-cut)：即整个流网络中，容量最小的那个割(st cut).

最大流 Max-flow

定义 流 st-flow (flow) 中 $f$ 是一个满足以下条件的函数：

• 每一个$e\in E$，均有$0<=f(e)<=c(e)$ ，即流量小于等于容量。
• 对于任意 $v\in V-s,v$，即出去源点和汇点的其他点：${\sum }_{eintov}f(e)={\sum }_{eioutofv}f(e)$，即出去源点和汇点，所有进入点的流量等于流出点的容量。

进入v的流量：$5+5+0=13$、流出v的流量：$10+0=10$

流 flow 的值定义为：$val(f)={\sum }_{eoutofs}f(e)-{\sum }_{eintos}f(e)$

下图中，网络流的值为：$10+5+10=25$

最大流Max-flow：流网络中，值最大的流即为最大流。

最大流问题 和 最小割问题 问题是等价的。

Greedy algorithm

增广路径 Augmenrt Path：从 源点 s 到 汇点 t 的一条简单路径，路径上任意一条边均满足$f(e)<c(e)$。
阻塞流 Blocking Flow：如果一个 流 flow，找不到增广路径，则该流称为阻塞流。最大流一定是阻塞流，但阻塞流不一定是最大流。

贪心算法的流程：

• 初始流上，任意的$e\in E,f(e)=0$。
• 进行流量的增加：
  • 寻找该流上的增广路径 P
  • 增加 增广路径 P 上各个边的流量
• 重复流量增加的步骤，直至该流变成阻塞流

贪心算法得到的阻塞流并不一定是最大流，因为贪心在寻找增广路径之后，直接沿着找到的增广路径进行流量的增加，之后就继续找下一条增广路径。没有考虑增广路径找错的情况，没有办法减少增广路径上的错误流量。

Ford–Fulkerson algorithm

剩余网络 Residual network

原始边 Original edge：$e=(u,v)\in E$，且边上的流量：$f(e)$、边上的容量:$c(e)$

反向边：$e^{reverse}=(v,u)$
剩余容量：$$c_f(e)=\{\begin{array}{ll}c(e)-f(e)& e\in E\\ f(e^{reverse})& e^{reverse}\in E\end{array}$$

剩余网络 Residual network：$G=(V,E_f,s,t,c_f)$：

• E f = { e : f ( e ) < c ( e ) } ∪ { e : f ( e r e v e r s e ) > 0 } E_f = \{e: f(e) < c(e)\} ∪ \{e: f(e^{reverse}) > 0\} Ef​={e:f(e)<c(e)}∪{e:f(ereverse)>0}

定义增广路径 的 瓶颈容量 为 增广路径上，最小的剩余容量。

Ford–Fulkerson algorithm算法流程

• 初始流上，任意的$e\in E,f(e)=0$。
• 进行剩余图上流量的增加：
  • 寻找该剩余图上的增广路径 P
  • 增加 增广路径 P 上各个边的流量，同时在剩余图上添加反向变
• 重复流量增加的步骤，直至该流变成阻塞流

算法的流量增减都是在剩余图上进行操作的。

最大流最小割理论 max-flow min-cut theorem

定义 $f$ 为任意的 流 flow，$(A,B)$ 为任意的 割 cut，则$f$的流量大小等于流过$(A,B)$的流量。
$$val(f)=\sum _{eoutofA}f(e)-\sum _{eintoA}f(e)$$

$$\begin{gathered} val(f)=\sum _{eoutofA}f(e)-\sum _{eintoA}f(e) \\ val(f)=\sum _{eoutofs}f(e)-\sum _{eintos}f(e) \\ =\sum _{v\in A}(\sum _{eoutofA}f(e)-\sum _{eintoA}f(e)) \\ =\sum _{eoutofA}f(e)-\sum _{eintoA}f(e) \end{gathered}$$

同时定义 $f$ 为任意的 流 flow，$(A,B)$ 为任意的 割 cut，则$val(f)<=cap(A,B)$
$$val(f)=\sum _{eoutofA}f(e)-\sum _{eintoA}f(e)<=\sum _{eoutofA}f(e)<=\sum _{eoutofA}c(e)=cap(A,B)$$

定义 $f$ 为任意的 流 flow，$(A,B)$ 为任意的 割 cut。如果 $val(f)=cap(A,B)$，那 $f$ 一定是最大流，$(A,B)$一定是最小割。

Max-flow min-cut theorem：Value of a max flow = capacity of a min cut.

容量扩展算法 capacity-scaling algorithm

时间复杂度分析 Analysis of Ford–Fulkerson algorithm

假设 流网络 中所有的边上的容量均为整数，且 范围是 1~C。
则 FFA算法中，每一条边的流量和剩余容量也都是正整数。

假设 $f\ast$ 是某流网络的最大流，则该流网络中最大流流量 $val(f\ast )<=nC$。

又每次增广路径最少也会增加 1 的流量，假设使用 BFS、DFS来寻找增广路径，时间复杂度为 $O(m)$，则Ford–Fulkerson algorithm 的时间复杂度最坏为：$T(n)=O(mnC)$

$T(n)=O(mnC)$的情况出现在，每一次找到的增广路径都只能增加一个容量，例如：

如果时间复杂度为 $O(mnC)$，那么该时间复杂度并非多项式时间的，需要根据边的数量以及容量的大小来判断是否能在一定时间内解决。

优化：选择合适的增广路径

出现上述非多项式时间的时间复杂度的情况的原因：每一次增广路径都只增加1个流量，即瓶颈容量为1的增广路径。
因此我们可以选择更合适的增广路径。

• 最大瓶颈容量的增广路径
• 足够大的瓶颈容量的增广路径
• 最短路径的增广路径

选择足够大瓶颈容量的增广路径算法：Capacity-scaling algorithm

算法大致流程：

• 首先遍历所有的边，得到最大容量/2，将其设置为当前瓶颈容量下限 k
• 在剩余图中寻找瓶颈容量大于等于 k 的增广路径
  • 如果找到了就执行FFA算法
  • 如果找不到了，就将 k 减小到原来的一半
• 一直执行寻找增广路径的循环，直至 k 变为1，此时所有的增广路径都能正常寻找到。

算法伪代码：

m：边的数量
n：点的数量
C：容量的上限
使用该算法寻找增广路径，总的寻找最大流的时间复杂度：$$T(n)=O(m^{2}logC)$$

寻找最短增广路径算法：BFS

使用队列，不断扩展下一个节点，当到达 t ，此路径即为最短路。

算法伪代码：

m：边的数量
n：点的数量
C：容量的上限
使用该算法寻找增广路径，总的寻找最大流的时间复杂度：$$T(n)=O(m^{2}n)$$

其他算法的时间复杂度