Mengzelev's Blog

算法导论学习笔记-最大流

Word count: 1,519 / Reading time: 6 min
2018/12/05 Share

流网络

流网络

  • 有向图$G=(V,E)$
  • 图中中每条边$(u,v)\in E$有一个非负的容量值$c(u,v)\ge 0$
  • 如果$(u,v)\notin E$,定义$c(u,v)=0$
  • 如果边集合$E$包含一条边$(u,v)$,则图中不存在反方向的边$(v,u)$
  • 源结点$s$汇点$t$
  • 流网络图是连通的
  • 除源结点外的每个结点都至少有一条进入的边,$|E|\ge |V|-1$

设$G=(V,E)$为一个流网络,其容量函数为$c$。设$s$为网络的源结点,$t$为汇点。$G$中的流是一个实值函数$f: V\times V \to \mathbb{R}$,满足下面两条性质:

  • 容量限制:对于所有的结点$u,v\in V$,要求$0\le f(u,v)\le c(u,v)$
  • 流量守恒:对于所有的结点$u\in V-{s,t}$,要求$$\sum\limits f(v,u)=\sum\limits f(u,v)$$当$(u,v)\notin E$时,从结点$u$到结点$v$之间没有流,因此$f(u,v)=0$

称非负数值$f(u,v)$为从结点$u$到结点$v$的流。(流入=流出)

一个流$f$的$|f|=\sum\limits_{v\in V}f(s,v)-\sum\limits_{v\in V}f(v,s)$ (从源结点流出的总流量减去流入源结点的总流量)

最大流问题:给定一个流网络$G$、一个源结点$s$、一个汇点$t$,找到值最大的一个流

反平行边

如果要使用反平行边来模拟一个流问题,就选择两条反平行边中的一条,加入一个新结点来将其分解为两段,并以新的结点到原来边的结点的两条路替换所选边,同时将两条新设立的边的容量设置为与原来的边的容量相同。

具有多个源结点和多个汇点的网络

加入一个超级源结点$s$和一个超级汇点$t$

Ford-Fulkerson方法

残存网络

给定流网络$G$和流量$f$,残存网络$G_f$由那些仍有空间对流量进行调整的边构成。

残存容量为$c_f(u,c)=c(u,v)-f(u,v)$

对正流量的缩减:将边$(v,u)$加入到图$G_f$中,并将其残存容量设置为$c_f(v,u)=f(u,v)$

残存容量的形式化定义如下:

给定一个流网络$G=(V,E)$和一个流$f$,则有$f$所诱导的图$G$的残存网络为$G_f=(V,E_f)$,其中$E_f={(u,v)\in V\times V: c_f(u,v)>0}$,有$|E_f|\le 2|E|$

递增:如果$f$是$G$的一个流,$f’$是对应的残存网络$G_f$的中的一个流,定义$$f’\uparrow f’:V\times V\to\mathbb{R}$$为流$f’$对流$f$的递增

抵消操作:在残存网络中将流量推送回去

引理26.1:$$|f\uparrow f’|=|f|+|f’|$$

增广路径

增广路径$p$:残存网络$G_f$中一条从源结点$s$到汇点$t$的简单路径

残存容量:在一条增广路径$p$上能够为每条边增加的流量的最大值$$c_f(p)=\min{c_f(u,v): (u,v)\in p}$$


流网络的切割

流网络的切割:将结点集合$V$划分为$S$和$T=V-S$两个集合,使得$s\in S, t\in T$

横跨切割的$(S,T)$的净流量$f(S,T)$:$$f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)-\sum\limits_{u\in S}\sum\limits_{v\in T}f(v,u)$$

切割$(S,T)$的容量:$$c(S,T)=\sum\limits_{v\in S}\sum\limits_{v\in T}c(u,v)$$
最小切割:整个网络中容量最小的切割

  • 对于容量,只计算从集合$S$发出进入集合$T$的边的容量,而忽略反方向边上的容量
  • 对于流,考虑从$S$到$T$的流量减去从$T$到$S$的反方向的流量

引理26.4:整个流网络的流量与横跨某一个切割的流量相等$$f(S,T)=|f|$$

推论26.5:$|f|\ge c(S,T)$

定理26.6(最大流最小割定理)

基本的Ford-Fulkerson算法

粗糙的时间复杂度上界:$O(E|f|)$($f$为将有理数流网络转换成整数流网络后,网络中的一个最大流)

Edmonds-Karp算法

在Ford-Fulkerson算法的第三行使用广度优先搜索来寻找增广路径。
每次在残存网络中选择的增广路径是一条从源结点$s$到汇点$t$的最短路径,其中每条边的权重为单位距离。

时间复杂度:$O(VE^2)$

引理26.7:使用Edmonds-Karp算法,对于除源结点和汇点外的所有结点$v$,残存网络$G_f$中的最短路径距离$\delta_f(s,v)$随着每次流量的递增而单调递增。

定理26.8:Edmonds-Karp算法所执行的流量递增操作的总次数为$O(VE)$

关键边:在残存网络中,一条路径$p$的残存容量是该条路径上边$(u,v)$的残存容量,即$c_f(p)=c_f(u,v)$
对于$E$的每条边来说,其成为关键边的次数最多为$|V|/2$次。

最大二分匹配

在一个二分图中,结点集合可以划分为$V=L\cup R$,其中$L$和$R$是不相交的,并且边集合$E$中所有的边都横跨$L$和$R$。

构造一个流网络$G=(V’,E’)$,其中$$V’=V\cup{s,t}$$$$E={(s,u):u\in L, u\in L}\cup {(u,v):(u,v)\in E}\cup {(v,t):v\in\mathbb{R}}$$
给$E’$中的每条边赋单位容量

流$f$是整数值的:对于所有的边$(u,v)\in V\times V$,$f(u,v)$都是整数值。

定理26.10(完整性定理Integrality theorem):如果容量函数$c$只能取整数值,则$Ford-Fulkerson$方法所生成的最大流$f$满足$|f|$是整数值的性质。而且,对于所有的结点$u$和$v$,$f(u,v)$都是整数。

推论26.11:二分图$G$中的一个最大匹配$M$的基数等于其对应的流网络$G’$中某一最大流$f$的值。

时间复杂度:$O(VE)$

CATALOG
  1. 1. 流网络
    1. 1.1. 流网络
    2. 1.2.
    3. 1.3. 反平行边
    4. 1.4. 具有多个源结点和多个汇点的网络
  2. 2. Ford-Fulkerson方法
    1. 2.1. 残存网络
    2. 2.2. 增广路径
    3. 2.3. 流网络的切割
    4. 2.4. 基本的Ford-Fulkerson算法
    5. 2.5. Edmonds-Karp算法
  3. 3. 最大二分匹配