首先最重要的,当然是了解一些信息: 网络(或者流网络,Flow Network)与 网络流(Flow)的概念。
网络
首先引用wiki定义
在图论中,网络流(英语:Network flow)是指在一个每条边都有容量(Capacity)的有向图分配流,使一条边的流量不会超过它的容量。通常在运筹学中,有向图称为网络。
简单来说,网络是个有向图 G=(V,E),这张图上每条边\((u,v)\in E\),都有各自的一个属性:容量(Capacity),也就是权值,这个属性代表的不是走过这条边带来的贡献,或者说价值,而是最大只能通过多少。
特殊的,当\((u,v)\notin E,c_{u,v}=0\)
同时,在一个网络中有两个特殊的点,源点(Source)s 和汇点(Sink)t。\(s,t\in V,(s\not=v)\)
流
流(flow)\(f_{u,v,}\)是定义在二元组\((u,v\in V)\)上的实数函数,表示\((u,v)\)这条边的流量,可以理解为这条边对整体的实际贡献,\(c_{u,v}-f_{u,v}\)表示剩余容量,整体网络的流量定义为:从源点S出发的流量总和(大小等于T的接受流量之和)。
而且流同时满足以下性质:
- 1.量限制:对于每条边,流经该边的流量不得超过该边的容量,即\(f_{u,v}\le c_{u,v}\)
- 2.对称性:每条边的流量与其相反边的流量之和为 0,即
- 3.流守恒性:从源点流出的流量等于汇点流入的流量,即\(∀x\in V-\{s,t\},\Sigma _{(u,x)}f(u,v)=\Sigma _{x,v}\in f(u,x)=\Sigma _{(x,v)\in E} f(x,v)\)
那么此时我们就可以得到函数完整定义:
网络流的几类问题
常见问题有三种:最大流,最小割,费用流,上下界网络流。
最大流
我们有一张图,要求从源点流向汇点的最大流量(可以有很多条路到达汇点),就是我们的最大流问题。
费用流(最小费用最大流)
最小费用最大流问题是这样的:每条边都有一个费用,代表单位流量流过这条边的开销。我们要在求出最大流的同时,要求花费的费用最小。
最小割
割其实就是删边的意思,当然最小割就是割掉x条边来让s跟t不互通。我们要求x1条边加起来的流量综合最小。这就是最小割问题。