文档介绍：图论算法
录火流问题
长沙市雅礼中学
朱全民
运输网络
现在想将一些物资从S运抵T,必须经过一些中转站。连接中
转站的是公路,每条公路都有最大运载量
每条狐代表一条公路,弧上的数表示该公路的最大运载量。
最多能将多少货物从S运抵T?
V1
V3
4
7
3
V2
V4
公路运输图
可行流
可行流
对于网络流图G,每一条孤()都给定一个非负数「,这
组数满足下列三条件肘称为这网络的可行流,用f表示
每一条孤()有fC
除源点S和汇点T以外的所有的点ⅵ,恒有:
∑()=Σ(f)
该等式说明中间点ⅵi的流量守恒,输入与翰出量相等。
∑(fs)=ΣT)=V0
可增广路
给定一个可行流仁印。着=C,称、Wy为饱和孤;否
则称<ⅵ,v>为非饱和狐。若=0,称<vy>为季流弧;否
则称<ⅵ,v>为非流弧。
定义一条道路P,起点是S、终点是T。把P上所有与P方向
致的弧定义为正向弧,正向弧的全体记为P+;把P上所
有与P方向相悖的孤定义为反向弧,反向孤的全体记为P-。
譬如在图中,P=(S,,V2V3,V4,T),那么
P+={<s,v|>,<V|,V2>,<V2,V3>,<V4,T>
P-={<V4,V3>
给定一个可行流f,P是从S到T的一条道路,如果满足
千是非饱和流,并且>∈P,与是非零流,并且41>∈P
那么就称P是f的一条可增广路。之所以称作“可增户”,
是因为可改进路上弧的流量通过一定的规則修改,可以令
整个流量放大
剩余图(残余网络)
剩余郾G’=(,E)
流量网络G=(V,E)中,对于任意一条边(a,b),若
flow(a, b <capacity(a, b)or flow(b,a)>0
则(ab)∈E
可以沿着a->b
方向增丿
剩余图的权值代表能沿边增广的大小
有向图
Capacity=5
Capacit
Capacity=6
Flow=2
Flow=2
Flow=2
4
余○
●剩余图中,每条边都可以沿其方向增广
●剩余图中,从源点到汇点的每一条路径都对应一条
增广路
G=(V,E,C是已知的网絡流图,设∪是V的一个子集,W
U,满足S∈∪,T∈W。即∪、W把V分成两个不相
交的集合,且源点和汇点分属不同的集合。
对于弧尾在∪,弧头在Ⅵ的弧所构成的集合称之为剖切,
用(U,w)表示。把劃切(U,W)中所有弧的容量
之和叫做此劃切的容量,记为C(U,W),即
CU,W)=∑c
割切示例
上例中,令U={S,V1},则W={V2,V3,Ⅵ4,T,那么
C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>
=8+4+4+1=17
流量算法的基本理论
定理丨:对于已知的网络流图,设任意一可行流为f
任意一剖切为(UW),必有:V(≤c(U,w
定理2:可行流「是录火流的充分必要条件是:f中不
存在可改进路。
定狸3:整流定理。
如果网络中所有的弧的容量是整教,则存在整教值
的录大流。
定理4:录大流录小制定理。
最大流等于最小剡,即maxV(f=minc(U,w