网络流

网络流简介#

容量网络#

网络：指一个有向图 $G(V,E)$ .

容量：在 $G$ 中，称每条边 $(u, v)$ 的权值 $c(u, v)$ ，为这条边的容量；特殊的，若 $(u,v)\notin E$ ， $c(u, v)=0$ .

源点和汇点： $V$ 中的两个特殊点。一般记 $s$ 为源点， $t$ 为汇点， $s\neq t$ .

流#

流函数#

网络 $G$ 的流函数是定义在二元组( $u\in V, v\in V$ )上的实数函数 $f(u, v)$ .

f(u,v)= \left\{ \begin{aligned} &f(u,v),&(u,v)\in E\\ &-f(v,u),&(v,u)\in E\\ &0,&(u,v)\notin E,(v,u)\notin E \end{aligned} \right.

定义#

对于 $(u, v)\in E$ ， $f(u, v)$ 称为边的流量， $c(u, v)-f(u, v)$ 称为边的剩余流量。

整个网络的流量为 $\sum_{(s, v)\in E} f(s, v)$ ，也就是从源点出发的所有流量的和。

性质#

$f(u, v)$ 满足以下三条性质：

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 $f(u,v)\leq c(u,v)$ ;
斜对称性：每条边的流量与其相反边的流量之和为 $0$ ，即 $f(u,v)=-f(v,u)$ ;
流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V\setminus\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$ .

最大流#

概述#

在一个流量网络中，求从源点 $s$ 流向汇点 $t$ 的最大流量。流量定义为：从源点出发的所有流量的和。

Ford-Fulkerson 增广路算法#

通过寻找增广路来更新最大流。注意：这里的增广路与二分图中的增广路定义不同。

残量网络#

残量：给定容量网络 $G(V, E)$ 及可行流 $f$ ， $(u, v)$ 上的残量记为 $c_f(u, v)=c(u, v)-f(u, v)$ .

对于每条边而言，残量为这条边可以增加的容量。

残量网络：对于容量网络 $G(V, E)$ 及其上的网络流 $f$ ， $G$ 关于 $f$ 的残量网络为 $G_f(V_f, E_f)$ . $(u, v)\in E_f$ 的边权记为 $c_f(u, v)$ . 残量网络 $G_f$ 满足：

$V_f=V$
对于任意 $(u, v)\in E$ ，如果 $f(u, v) < c(u, v)$ ，那么 $(u, v)\in E_f$ 且 $c_f(u, v) = c(u, v) - f(u, v)$ .
对于任意 $(u, v)\in E$ ，如果 $f(u, v) > 0$ ，那么 $(v, u)\in E_f$ 且 $c_f(v, u)=f(u, v)$ .

通俗的来说，比如对于一条边 $(u, v)$ ， $f(u, v)=3$ ， $c(u, v)=5$ 。这条边的流量最多可以再增加 $2$ ，所以残量网络中 $c_f(u, v)=2$ ；同时，这条边的流量最多可以减少 $3$ ，又因为 $v$ 向 $u$ 增加流量，等价于 $u$ 向 $v$ 减少流量，所以在残量网路中的体现就是 $c_f(v, u)=3$ 。