流网络 $ G=(V,E) $
一些基本概念
- V: 点集. E: 边集.
- 是一个有向图,有一个源点 $s$ 和一个汇点 $t$
- 不考虑反向边, 如果有反向边,就在反向边上加一个点.这样两点之间的来回就变成了三点的环.
- 对于不存在的边$(u,v)$,定义容量 $ c(u,v) = 0\ $ $(u,v \in V)$
-
可行流 $f$ 要满足 (注意这里也不考虑反向边), $f$表示一组可行的方案:
1) 容量限制 $ 0\le f(u,v) \le c(u,v)$
2) 流量守恒,对于任意 $V_x \in V/\{s,t\}$ 有 $\sum_{(v,x)\in E} f(v,x) = \sum_{(x,u)\in E}f(x,u)$ -
可行流的流量值 $\left\vert f\right\vert = \sum_{(s,v)\in E} f(s,v) - \sum_{(v,s)\in E}f(v,s)$ 表示从 $s$ 到 $t$ 的流量值是多少。 可行流的流量值就是从源点净流出的流量值,也是净流入汇点的流量值。
-
最大流 指的是所有可行流里面流量最大的可行流, 也叫 最大可行流.
-
残留网络(残量网络) 是针对流网络的某一条可行流来说的。可行流同,残留网络也不同。
- 记作 $G_f$ , 包括点集 $V_f = 流网络中的所有点\{V\}$, 边集 $E_f = \{E\ 和所有\ E\ 中边的反向边\}$。所以$E_f$中边的数量是$E$中边的数量的两倍。
-
残留网络的边$(u,v)$的容量$c’(u,v)$ 定义为:
- $c(u,v) - f(u,v)\ ,\ (u,v) \in E$ 即如果$(u,v)$是原图中的边,那么它在残留网络中的容量定义为原图中的容量 减去 流量
- $f(v,u)\ ,\ (v,u) \in E$ 即如果 $(v,u)$ 是原图中的边,那么 $(u,v)$ 就是反向边,$(u,v)$ 在残差网络中的容量定义为 $(v,u)$ 的流量 $f(v,u)$。
- 注意,为什么使用原边在当前可行流方案下的流量作为残留网络反向边的容量?这样当前可行流方案对应的残留网络中的原图的反向边作为提供 “反向” 流量的载体。
- 怎么理解 “反向” 流量?如下图所示,蓝色数字为原图的边容量,红色数字是一组可行流,绿色是可以增加流量的方案。那么绿色的方案里中间的边的流量是与当前可行流的方向”相反”的。
-
残留网络 示例
- 原图,蓝色为容量,红色为每条边在当前可行流的流量。
- 对应当前可行流的残留网络,蓝色为正向边(即原图的边)及其在残留网络中的容量,红色为反向边及其在残留网络中的容量:
-
原图的可行流 $f$ 与 对应的残留网络的可行流 $f’$的关系
-
$f + f’$ 也是原网络的一个可行流
- 注意这里 $f’$ 是由 $f$ 决定的,然后 $f + f’$ 又是原图的一个可行流。
- 从可行流的两个性质角度来证明:
- 容量限制
- 对于残留网络中的正向边 $(u,v)$, 有$0 \le f’(u,v) \le c’(u,v) = c(u,v) - f(u,v) \Rightarrow 0 \le f’(u,v) + f(u,v) \le c(u,v)$ 满足容量限制
- 对于残留网络中的反向边 $(u,v)$, 有$0 \le f’(u,v) \le c’(u,v) = f(v,u) \le c(v,u)$ 满足容量限制
- 流量守恒
- 原图中和残留网络中每个点都是流量守恒的,所以相加之后的可行流还是流量守恒的。
- 容量限制
-
可行流的和的流量 = 流量的和 $\left\vert f + f’ \right\vert = \left\vert f \right\vert + \left\vert f’ \right\vert $
- 流量相加的定义是原图中每一条边(不考虑反向边,上面讲了反向边的处理方法)与残留网络中对应的两条边(正向边和反向边)的流量相加。
- 上面的符号有一点不好,因为残留网络中反向边的流量对于正向边来讲是个负值。
- 那么残留网络的流量为正的话,表示原图中可行流的流量还可以增大,增大的量就是残留网络的流量。(注意可行流的流量 $f$ 的定义是源点净流出或者汇点净流入的流量)
-
-
增广路径
- 在残留网络中从源点出发,沿着流量大于0的边,如果能到达汇点,那么这条路径就叫做增广路径。一般指的是一个有向无环路径
- 二分图中的增广路径也是这个意思,二分图问题也可以用最大流解决。
- 定理:如果在可行流 $f$ 的残留网络 $G_f$ 中没有增广路径,则 $f$ 是原图的一个最大流。(证明会用到后面学的“割”)。
- 在残留网络中从源点出发,沿着流量大于0的边,如果能到达汇点,那么这条路径就叫做增广路径。一般指的是一个有向无环路径
-
割(切割)
-
割也是对于原网络来说的,所以也不存在反向边。
-
定义: 把点集 $V$ 分成两部分 $S$ 和 $T$, 并满足:
- $s \in S, t\in T, S \cap T = \emptyset$
- $S$ 中的点不一定连同,$T$ 中的点也不一定连通。
-
割的容量
- 所有从 $S$ 指向 $T$ 的边的容量之和,记作 $c(S,T) = \sum_{u \in S}\sum_{v \in T}c(u,v)$
- 一个节点数为 $n$ 的图的割的数量是$2^{n-2}$,即除了源点和汇点以外 $n-2$ 个节点,每个节点可以选在 $S$ 集合或者 $T$ 集合。
- 最小割 指所有的割里面的容量的最小值
-
割的流量
- $f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{v \in T}\sum_{u \in S}f(v,u)$ ,即所有从 $S$ 到 $T$ 的边的流量和 减去 所有从 $T$ 到 $S$ 的边的流量和.
-
注意 割的容量只涉及$S$ 指向 $T$ 的边的边,割的流量涉及从 $S$ 到 $T$ 和 从 $T$ 到 $S$ 的边。
-
割的性质
- $\forall [S,T], \forall f(S,T), f(S,T) \le c(S,T)$ 任一割的任一流量小于它的容量。
- 一个割确定之后它的容量就确定了,但是流量方案有很多个。
- 不论哪个流量方案,都不会大于当前割的容量。
-
$f(S,T) = \left\vert f \right\vert$ 从 $S$ 到 $T$ 的流量等于从源点流出的流量,即可行流的流量。
-
从一个集合 $X$ 到另一个集合 $Y$ 的流量定义为: $f(X,Y) = \sum_{u \in X}\sum_{v \in Y}f(u,v) - \sum_{v \in Y}\sum_{u \in X }f(v,u)$
- 性质1: $f(X,Y) = -f(Y,X)$
- 性质2: $f(X,X) = 0$
- 性质3: $X \cap Y = \emptyset \Rightarrow f(Z,X \cup Y) = f(Z,X) + f(Z,Y)$
- 性质4: $X \cap Y = \emptyset \Rightarrow f(X \cup Y, Z) = f(X,Z) + f(Y,Z)$
-
证明 $f(S,T) = \left\vert f \right\vert$
- $S \cup T = V (S与T的并集是全部点集V),\ S \cap T = \emptyset \newline\Rightarrow f(S,V) = f(S,S) + f(S,T)\newline\Rightarrow f(S,T) = f(S,V) - f(S,S)\newline\qquad\qquad= f(S,V) \newline\qquad\qquad= f(\{s\},V) + f(S - \{s\},V)$
- $S’ = \{S - \{s\}\}$ 是 $S$ 中不包括源点的所有点的集合。因为没有源点参与,所以这个集合到 $V$ 中的流量为0,即流入等于流出 $f(S’,V) = 0$
- $f(S’,V) = \sum_{u \in S’}\sum_{v \in V}f(u,v) - \sum_{u \in S’}\sum_{v \in V}f(v,u)\newline\qquad\qquad=\sum_{u \in S’}\left(\sum_{v \in V}f(u,v) - \sum_{v \in V}f(v,u)\right)\newline$ 对于非源点 / 汇点有流量守恒,即流入=流出. 所以 $\left(\sum_{v \in V}f(u,v) - \sum_{v \in V}f(v,u)\right) = 0$ , 即 $f(S’,V) = 0$
- $\left\vert f \right\vert = f(S,T) \le c(S,T)$ , 即任一可行流总是不大于任一割的容量。所以最大可行流的流量 不大于 最小割的容量。
-
- $\forall [S,T], \forall f(S,T), f(S,T) \le c(S,T)$ 任一割的任一流量小于它的容量。
-
最大流最小割定理 : 下面三个条件互为等价,即知道其中一个,能推出另外两个。
1) 可行流 $f$ 是最大流
2) 可行流 $f$ 的残留网络 $G_f$ 中不存在增广路
3) 存在某个割 $\exists [S,T], \left\vert f \right\vert = c(S,T)$ 即 可行流的流量与某个割的容量相等。-
$1) \Rightarrow 2)$ 反证法:假设对于最大可行流 $f$ 的残留网络 $G_f$ 存在增广路径,则 $G_f$ 有可行流 $\left\vert f’ \right\vert \lt 0$. 于是得到 $\left\vert f + f’ \right\vert = \left\vert f \right\vert + \left\vert f’ \right\vert \lt \left\vert f \right\vert$, 即原图还有更大的可行流 $f + f’$ ,与假设矛盾!
-
$3) \Rightarrow 1)$, $\left\vert f \right\vert \le \left\vert f_{max} \right\vert, \left\vert f_{max} \right\vert \le c(S,T) = \left\vert f \right\vert \Rightarrow \left\vert f \right\vert = \left\vert f_{max} \right\vert$ ,即可行流 $f$ 的流量小于等于最大流的流量,最大流的流量又小于任一割的容量,$f$ 的流量又等于某个割的容量,那么得出可行流的流量等于最大流的流量。
-
$2) \Rightarrow 3)$, 当 $G_f$ 不存在增广路径的前提下,尝试在原网络中构造一个割,使其容量等于可行流的流量。
- 构造集合 $S$: 在 $G_f$ 中从 $s$出发沿容量大于0的边走,所有能走到的点。由于 $G_f$ 不存在增广路径,所以 $t \notin S$.
- 构造集合 $T = V - S$
- $[S,T]$ 构成合法的割。
- $\forall x\in S, y\in T$ 则在原网络中必有 $f(x,y) = c(x,y)$ , 因为如果 $f(x,y) \lt c(x,y)$,说明在 $G_f$ 之中边 $(x,y)$的容量大于0,即从 $x \in S$ 沿着容量大于0的边能走到 $y$, 那么 $y$ 也应该在 $S$ 里面,但是取点的时候 $y \in T$, 所以从 $x \in S$ 沿着容量大于0的边不能走到 $y$, 即$G_f$ 之中边 $(x,y)$的容量等于0,那么在原网络中必有 $f(x,y) = c(x,y)$ .
- $\forall b\in S, a\in T$ , 在原网络中必有 $f(a,b) = 0$. 因为如果 $f(a,b) \gt 0$, 那么在$G_f$中的反向边的容量 $c(b,a) \gt 0$, 即 $a \in S$, 得到矛盾!!所以在原网络中必有 $f(a,b) = 0$.
- 根据割的流量的定义和性质, 有 $\left\vert f \right\vert = f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{v \in T}\sum_{u \in S}f(v,u)$.
又因为上面推出了 $\forall v \in T, u \in Sf(v,u) = 0$,
得到 $\left\vert f \right\vert = f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) = \sum_{u \in S}\sum_{v \in T}c(u,v)$ (上面证明了$\forall x\in S, y\in T, 原网络中有 f(x,y) = c(x,y)$),
根据割的容量的定义 $c(S,T) = \sum_{u \in S}\sum_{v \in T}c(u,v)$,
得到 $\left\vert f \right\vert = f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) = c(S,T)$
-
-
E-K算法 $O(nm^2)$
-
基本思路:
- 根据当前可行流方案确定残留网络,并在残留网络中寻找增广路.
- 如果找不到增广路,则当前可行流方案为最大流.
- 如果找到增广路,根据增光路更新可行流方案,回到第 1 步继续迭代.
-
最大流的代码维护的是残留网络,所以都是建双向边。存图用邻接表。
- 注意加边的时候正反向边一起加,这样正向边编号是i,反向边编号就是i^1. 例如正向边编号是0,对应的反向边编号就是1.下一组正向边编号就是2,对应的反向边就是3。别的方法也可以,只要保证每条正向边都能$O(1)$时间找到对应的反向边即可。
while (k != 0) {
在当前的残留网络中找增广路(从起点BFS看能不能到终点就可以了);
得到增广路径能增加多少流量 k (就是增广路径上边的在原网络中容量的最小值);
更新残留网络正/反向边的容量(因为上一步得到原图中正向边的流量+k, 所以正向边的容量-k, 反向边的容量+k);
}
- 时间复杂度: $O(nm^2)$,即 $点数 \times 边数的平方$,是费用流的主要算法。