网络流——概念篇

网络

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

每条边 \((u,v)\in E\)都有一个权值\(c(u,v)\),称之为容量,对于$(u,v)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. 流守恒性:从源点流出的流量等于汇点流入的流量,即 $xV-{s,t}, {{(u,x)E}}f(u,x)={{x,vE}}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)=\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.\)

网络流的常见问题

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

最大流

我们有一张图,要求从源点流向汇点的最大流量(可以有很多条路到达汇点),就是我们的最大流问题。

最小费用最大流

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

最小割

割其实就是删边的意思,当然最小割就是割掉 X 条边来让 S 跟 T 不互通。我们要求 X 条边加起来的流量总和最小。这就是最小割问题。

残量网络

首先我们介绍一下一条边的剩余容量 \(cf(u,v)\),它表示的是这条边的容量与流量之差,即 \(cf(u,v)=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