本文是网络流的一些基础内容

前置知识

定义

网络流算法中的一些定义

网络流图

如果带权有限的有向图 $G=(V,E)$ 满足如下条件，则称之为 网络流图

有且仅有一个节点 $S\in V$ 入度为 $0$ ，称为源点
有且仅有一个节点 $T\in V$ 出度为 $0$ ，称为汇点
$\forall ( u , v ) \in E \quad \exists c ( u , v ) \in \mathbb R ^ { + }$ 成为这条弧的容量。特别地，若 $(u,v)\notin E$ ，可以假定 $c(u,v)=0$

弧

弧是网络流图中的一条带权边 $(u,v)\in E$

流量

通过网络流图的一条弧 $(u,v)$ 的流量，通常记为 $f(u,v)$

网络流

一个流量的集合 $F = \{ f ( u , v ) \}$ 包含所有弧上的流，则称为这个网络流图的一个 网络流

可行流

在网络流图中满足下面条件的网络流称为 可行流

流量限制： $f(u, v) \leq c(u, v)$
流守恒： $\forall u \in V - \{ s , t \} , \sum _ { w \in V } f ( u , w ) = 0$

剩余流量

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

残量网络

所有边都是它的残量的网络 $G_f(V,E_f)$ 称为 残量网络，它用于显示可用的容量有多少

最大流

对于一个网络流图，它最大的可行流即为它的 最大流

网络流的性质

在任意时刻， $G$ 的网络流都满足如下性质

容量限制

通过一条弧的流量不能超过这条弧的容量上限

$\forall u , v \in V , \;f ( u , v ) \leq c ( u , v )$

反对称性

从一个结点 $s$ 到另一个结点 $t$ 的净流量一定是从 $t$ 到 $s$ 净流量的相反数

$\forall u,v\in V,\;f(u,v)=-f(v,u)$

流守恒

对于 $G$ 中任意一个结点 $u$ ,如果它既不是源点也不是汇点，那么它到相邻结点的所有流量之和为 $0$

$\forall u \in V - \{ s , t \} , \sum _ { w \in V } f ( u , w ) = 0$

最大流

残量网络

首先对于残量网络 $G_f$ ，与 $G$ 的区别在于每条边修改为了 剩余流量，也就是容量与当前流量的差，所以弧 $(u, v)$ 就是 $c_f(u, v) = c(u, v) - f(u, v)$

残量网络包含原图 $G$ 中的 反向边 ，用于撤销非最大的可行流，也就是 $c_f(v,u)=f(u,v)$

增广

定义对于残量网络中的流 $f,f'$ 上的增广操作 $f \uparrow f ^ { \prime }$ 为:

$\left( f \uparrow f ^ { \prime } \right) ( u , v ) = \left\{ \begin{array} { l l } { f ( u , v ) + f ^ { \prime } ( u , v ) - f ^ { \prime }(v,u ) } & { \text { if } ( u , v ) \in E } \\ {0}&{ \text { otherwise } } \end{array} \right.$

现在考虑证明 $\left( f \uparrow f ^ { \prime } \right) ( u , v )$ 是一个流

先来看容量限制:

$\begin{align}&\forall (u,v)\in E, c_f(v,u)=f(u,v)\\&\Rightarrow f'(v,u)\leq c_f(v, u) =f(u,v) \end{align}$ $\begin{aligned} \left( f \uparrow f ^ { \prime } \right) ( u , v ) & = f ( u , v ) + f ^ { \prime } ( u , v ) - f ^ { \prime } ( v , u ) \\ & \geqslant f ( u , v ) + f ^ { \prime } ( u , v ) - f ( u , v ) = f ^ { \prime } ( u , v ) \\ \left( f \uparrow f ^ { \prime } \right) ( u , v ) & = f ( u , v ) + f ^ { \prime } ( u , v ) - f ^ { \prime } ( v , u ) \\ & \leqslant f ( u , v ) + f ^ { \prime } ( u , v ) \\ & \leqslant f ( u , v ) + f ^ { \prime } ( u , v ) \\ & \leqslant f ( u , v ) + c ( u , v ) - f ( u , v ) = c ( u , v ) \end{aligned}$

接下来证明流守恒：

$\forall u \in V - \{ s , t \}$ ，有

$\begin{align} \sum _ { w \in V } \left( f \uparrow f ^ { \prime } \right) ( u , w ) &= \sum _ {w \in V} f ( u , w ) + f ^ { \prime } ( u , w ) - f ^ { \prime } ( w, u ) \\&=\sum _ {w \in V} f ( u , w ) + \sum _ {w \in V} f ^ { \prime } ( u , w ) - \sum _ {w \in V} f ^ { \prime } ( w , u )\end{align}$

由于 $f, f'$ 都是流，满足流守恒，故

$\begin{align} \sum _ { w \in V } \left( f \uparrow f ^ { \prime } \right) ( u , w ) &= \sum _ {w \in V} f ( u , w ) + \sum _ {w \in V} f ^ { \prime } ( u , w ) - \sum _ {w \in V} f ^ { \prime } ( w , u )\\ & = 0 + 0 + 0 = 0\end{align}$

定义这个的目的是这个东西有一个十分棒的性质:

$|f\uparrow f'|=|f|+|f'|$

证明：

把反向边拎出来然后用上面的性质就好了

令 $V_1=\{v:(s,v)\in E\}$ , $V_2=\{v:(v,s)\in E\}$ ，那么就有 $V_1\cap V_2 = \emptyset$ ， $V_1 \cup V_2 = V$

$\begin{align}|f\uparrow f'|&=\sum_{v\in V}(f\uparrow f')(s,v)-\sum_{v\in V}(f\uparrow f')(v,s)\\&=\sum_{v\in V_1}(f\uparrow f')(s,v)-\sum_{v\in V_2}(f\uparrow f')(v,s)\\&=\sum_{v\in V_1}\left(f(s,v)+f'(s,v)-f'(v,s)\right)\\&\qquad\qquad +\sum_{v\in V_2}\left(f(v,s)+f'(v,s)-f'(s,v)\right) \\&=\left(\sum_{v\in V_1}f(s, v)-\sum_{v \in V_2}f(v,s)\right)\\&\qquad\qquad +\left(\sum_{v\in V_1\cup V_2}f(s, v)-\sum_{v \in V_1\cup V_2}f(v,s)\right)\end{align}$

注意到上面 $\sum$ 中 $V_1, V_2, V_1\cup V_2$ 都可以被换为 $V$

故有

$\begin{align}|f\uparrow f'|&=\left(\sum_{v\in V}f(s, v)-\sum_{v \in V}f(v,s)\right)\\&\qquad\qquad +\left(\sum_{v\in V}f(s, v)-\sum_{v \in V}f(v,s)\right)\\&=|f|+|f'|\end{align}$

增广路

通过残留网络 $G_{f}$ 的从源点 $S$ 到汇点 $T$ 的一条有效路径被称为 增广路

增广路的流量被定义为 $c_f(p)=\min(c_f(u,v), (u,v)\in p)$

对于一次增广后，有

$|f\uparrow f'|=|f|+|f'|$

由于残量网络中保证 $c(u,v)>0$ ，故有

$|f\uparrow f'|=|f|+|f'|>|f|$

所以每次增广后流量增加

割

一个 $\text{s-t}$ 割 $C = (S, T)$ 是一种 $V$ 的划分使得 $s\in S, t\in T$ 。 $C$ 的割集是集合

当 $C =\emptyset$ 的时候，代表没有一条边 $(u,v)$ 有 $s\in S, t\in T$ ，所以 $|f| = 0$

下面来定义一些概念:

$f(s,t)$ 表示割 $(s,t)$ 之间的网络流，也就是

$f ( S , T ) = \sum _ { u \in S } \sum _ { v \in T } f ( u , v ) - \sum _ { u \in S } \sum _ { v \in T } f ( v , u )$

$c(s,t)$ 表示 $(u,v)$ 之间的容量，也就是

$c ( S , T ) = \sum _ { u \in S } \sum _ { v \in T } c ( u , v )$

注意到对于任意流 $f$ ，任意割之间的网络流量其实是不变的，即

$f(s,t)=|f|$

只会感性理解...求证明

一个小结论:

任意流 $f$ 的流量不超过任意割的容量 ，就是 $|f|\leq c(S,T)$

$\begin{aligned} | f | & = f ( S , T ) \\ & = \sum _ { u \in S } \sum _ { v \in T } f ( u , v ) - \sum _ { u \in S } \sum _ { v \in T } f ( v , u ) \\ & \leq \sum _ { u \in S } \sum _ { v \in T } f ( u , v ) \\ & \leq \sum _ { u \in S } \sum _ { v \in T } c ( u , v ) \\ & = c ( S , T ) \end{aligned}$

上式当且仅当 $\forall (u,v),u\in S, v\in T \text{ 且 } f(v,u)=0,f(u,v) = c(u,v)$ 时取等号，也就是 $S$ 流向其他点的流量达到饱和或为 $0$

最大流最小割定理

最大流最小割定理 提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和

设 $f$ 达到最大流，令 $G_f$ 是 $f$ 的残留网络，定义

$A$ ：在 $G_f$ 中可以从 $s$ 出发到达的点
$A^c$ ： $A$ 以外的点，即 $V − A$

换句话说， $v\in A$ 当且仅当 $v=s$ 时可以流出更多流量到 $v$

我们用反证法分别证明以上两点：

假设存在从 $A$ 流向 $A^c$ 的边 $(x,y)\in A\times A^{c}$ 并未达到饱和，即 $f(x,y)<c_{xy}$ 。因此，可以从 $x$ 流更多的流量到 $y$ ， $(x,y)$ 是 $G_f$ 的一条边。由 $x\in A$ 知 $G_f$ 图中有一条中的路径从 $s$ 到 $x$ ，其中只经过 $A$ 中的的点，所以 $y\in A$ ，产生矛盾。是故所有从 A 流向 Ac 的边流量均已达饱和
假设存在从 $A^c$ 流向 $A$ 的边 $(y,x)\in A^{c}\times A$ 其流量不为 $0$ ，即 $f(x,y)>0$ 。因此，可以从 $y$ 流更少的流量到 $x$ ， $(x,y)$ 是 $G_f$ 的一条边。由 $x\in A$ 知 $G_f$ 图中有一条中的路径从 $s$ 到 $x$ ，其中只经过 $A$ 中的的点，所以 $y\in A$ ，产生矛盾。是故所有从 $A^c$ 流向 $A$ 的边流量均为 $0$