网络流基础

¶ 定义

¶ 网络

有向图 $G=(V,E)$ 满足

• 有且仅有一个源点 $s \in V$，有且仅有一个汇点 $t \in V$，且 $s\not = t$
• 有一个函数 $c: V \times V \to R^+$
  每一条边对应容量 $c(u,v)$
  • 如果 $(u,v) \in E$ 且 $(v,u)\not\in E$ 则 $c(v,u) = 0$

$(u,v)$ 可称为弧

$c(u,v)$ 为弧的容量

可以类比水流，有很多只能单向流水的水管组成网络，水管有粗细 $c$

有一个有无限水流进入的源点 $s$，和无限水流出的汇点 $t$

¶ 网络流

定义函数 $f: V \times V \to R$，满足

容量限制

$f(u,v)\le c(u,v)$

反对称性

$f(u,v) = -f(v,u)$

流守恒 基尔霍夫电流定律

$\sum_{v\in V} f(u,v) = 0$

就是一种方案

你可以规定水管 $(u,v)$ 流 $f(u,v)$ 水

不能有没有规定过流量的水管

¶ 残量网络

边的剩余容量简称为残量，$c_f(u,v) = c(u,v) - f(u,v)$

通过残量我们可以构成残量网络 $G_f(V, E_f)$

我们有这样一个显然的结论，对于一个网络 $G$，有一个流 $f$，记此图的残量网络为 $G_f$，剩余容量为 $c_f$

残量网络上有一个流 $f'$

定义 $f\uparrow f'(u,v)=f(u,v)+f'(u,v)$

有 $f\uparrow f'$ 是原网络 $G$ 上的一个合法流

¶ 证明

十分简单，可略过

$$f(u,v)\le c(u,v)\\ f'(u,v)\le c_f(u,v)=c(u,v)-f(u,v)\\ f\uparrow f'(u,v)=f(u,v)+f'(u,v)\\ f\uparrow f'(u,v)\le f(u,v)+c(u,v)-f(u,v) = c(u,v)$$

证毕（其实只证了容量限制

就是一个网络各个弧的容量减去以用流量

算法中通常只存残量网络，每次直接在残量网络上修改

¶ 增广路

在残量网络上的一条路径 $(u_1, \cdots, u_k)$，满足

• $u_1 = s, u_k = t$
• $c_f(u_i, u_{i+1}) > 0$

显然，当残量网络无增广路时达到最大流

$\min\{c_f(u_i,u_{i+1})\}$ 称为增广流量

¶ 问题

¶ 最大流

定义 $\left | f \right | = \sum_{v\in V} f(s,v) = \sum_{v\in V} f(v, t)$

最大流就是求出最大的 $\left | f \right |$，有时候还求方案

水管网络最大的流速