图算法-最大流

1. 最大流

流网络：

源结点 s,汇点 t,每个结点都在从源结点到汇点的某条路径上

流网络G中的流 是一个实值函数f: V * V -> R

流满足两条性质：

(流量守恒：流入结点的总流量等于流出结点的总流量(除源结点与汇点以外))

流 f 的值 | f |

即从源结点流出的总流量减去流入源结点的总流量

最大流问题 ：给定一个流网络G、一个源结点、一个汇点，求值最大的流

残存网络 G_f由特定流网络G与流f产生

残存容量c_f(u,v):

理解: 图G中，若存在残存流量的边加入图G_f, 同时对不存在残存流量的边，将反向流量加入图G_f中

注： 残存网络并不是流网络，因不满足流网络的定义(可能同时存在双向的边)

举例:

(左边是流网络，右边是残存网络)

流网络中的一个流f对应残存网络中的一个流 f’ ,定义：

引理：

增广路径

2.最小割

流网络的切割
流网络G=(V, E)中的一个切割(S, T)将结点集合V划分为S和T=V-S两个集合，使得s属于S，t属于T

若f是一个流，则定义横跨切割(S, T)的净流量 f(S, T)如下：

切割(S, T)的容量是

一个网络的最小切割是整个网络中容量最小的切割

举例：

1. 对网络的一个流f, 网络的任意切割(S, T)都有切割的净流量等于流f的值，即f(S, T) = | f |
2. 流网络G中的任意流f的值都不能超过G中任意切割的容量，即 max | f | <= min f(S, T)

3.最大流最小割定理

求最大流/最小割： Ford-Fulkerson方法
基本的Ford-Fulkerson算法：

举例：