网络

网络表示一个有向图（可能有环），\(G=(V,E)\)。

每条边 \((u,v)\in E\) 都有一个权值 \(c(u,v)\)，称之为容量，对于 \((u,v)\notin E\)，均有 \(c(u,v)=0\)。

其中有两个点，\(s\in V\) 源点（没有入度）和 \(t\in V\) 汇点。（没有出度）

流

设 \(f(u,v)\) 定义在二元组 \((u\in V,v\in V)\) 上的实数函数且满足：

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

那么 \(f\) 称为网络 \(G\) 的流函数。对于 \((u,v)\in E\)，\(f(u,v)\)称为边的 流量，\(c(u,v)-f(u,v)\) 称为边的 剩余容量。

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

一般而言也可以把网络流理解为整个图的流量，而这个流量必满足上述三个性质。

流函数的完整定义

\[ f(u,v) = \begin{cases} f(u,v) & (u,v)\in E\\ -f(v,u) & (v,u)\in E\\ 0 & (u,v)\notin E,(v,u)\notin E \end{cases} \]

网络流的常见问题

网络流问题中常见的有以下三种：最大流，最小割，费用流。

最大流

我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点）。

最小费用最大流

每条边都有一个费用，代表单位流量流过这条边的开销。我们要在求出最大流的同时，要求花费的费用最小。

最小割

割其实就是删边的意思，就是割掉 \(X\) 条边来让 \(S\) 跟 \(T\) 不互通。我们要求 \(X\) 条边加起来的流量总和最小。

残量网络

一条边的 剩余容量 指条边还可以通过的流量，即 \(c(u,v)-f(u,v)\)，在实际应用中，我们也通常只关心剩余容量。

对于流函数 \(f\)，\(G_f\) 残量网络是网络 \(G\) 中所有结点 和剩余容量大于 \(0\) 的边构成的子图。

形式化的定义，即 \(G_f=(V_f=V,E_f=\left\{(u,v)\in E,c_f(u,v)>0\right\})\)。

注意，剩余容量大于 \(0\) 的边可能不在原图 \(G\) 中（根据容量、剩余容量的定义以及流函数的斜对称性得到）。可以理解为，残量网络中包括了那些还剩了流量空间的边构成的图，也包括虚边（即反向边）。

增广路

在原图 G 中若一条从源点到汇点的路径上所有边的 剩余容量都大于0 这条路被称为增广路。

或者说，在残量网络 \(G_f\) 中，一条从源点到汇点的路径被称为增广路。

参考：OI WIKI