算法分析与设计2005春.课件.第09讲.pdf

流网实例
1. 例1:管道中的流体
第九讲. Maximum Flow 2. 例2:电网中的电流
例:通信网络中的信息流
极大流 3. 3
4. 例4:装配线上的零件流
清华大学
宋斌恒
清华大学软件学院宋斌恒 1 清华大学软件学院宋斌恒 2
概念
1 2
1. 有向边:传输物质的管道
容量:每条管道有静态容量:单位时间
2. s t
内可以通过物质的最大数量,如每天可
以通过100万立方米的石油管道 3 4
3. 点:管道连接点,满足流量守恒律
清华大学软件学院宋斌恒 3 清华大学软件学院宋斌恒 4
流网的定义
电流定律
Kirchhoff’s 1. 流网G=(V,E)是一个具有非负边权的有向图,
边权c(u,v)叫做容量,如果(u,v)不属于E,我
: 们约定其容量c(u,v)=0。
2. 在流网上有两个特殊点源s和汇t。
流量
3. 对于每个点v,都有一条从s经过v到达t的路
对于电流就是定律
2. Kirchhoff’s 径
:计算流网中满足约束(上
述守恒律)的从源到汇的最大流量。
清华大学软件学院宋斌恒 5 清华大学软件学院宋斌恒 6
1
极大流问题
续 =(V,E)、流网上的容量c(u,v),和源
s、汇t,求流f使得其流值取得极大
流: 上的一个流是一个实函数:
4. Flow G f
V×VÆR, 它满足
:∑u∈V,f(u,v)>0f(u,v)
1. 容量约束:对所有u,v, f(u,v)≤c(u,v)
:∑u∈V,f(v,u)>0f(v,u)
2. 反对称:对所有u,v, f(u,v)=-f(v,u)
=总流出量-总流入量
3. 流守恒:对所有u∈V-{s,t} ∑ f(u,v)=0
v∈V :在非源非汇点,总流出量
4. 流f的值:|f| = ∑v∈Vf(s,v) =总流入量
5. f(u,v)叫做从u到v的流,其值可正可负
清华大学软件学院宋斌恒 7 清华大学软件学院宋斌恒 8
s1
多源多汇问题
许多实际问题是多源多汇问题【见下页图】,也就
是说流网中有多个源,有多个汇,这样的问题如何 s2 t1
解决?
我们通过添加人工源和汇的方法将多源多汇问题转
化为单源单汇的标准问题: 【见下下页图】
s3 t2
1. 添加人工源s和人工汇t两个节点,
2. 添加s到原问题所有源对应的顶点的有向边,并赋予
∞权,
3. 添加原问题所有汇对应顶点到t到有向边,并赋予∞ s4 t3
权,
4. 于是原问题就变成了标准单源单汇问题。Why
equivalent?
清华大学软件学院宋斌恒 9 s5 清华大学软件学院宋斌恒 10
s1 流的运算
设f是流函数,X和Y是V[G]的子集,
s2
t1 定义:f(X,Y)=∑x∈X, y∈Y f(x,y)
那么我们有:
1. 守恒律:对任意u属于V-{s,t}有