最大流算法.ppt

图论算法---最大流问题长沙市雅礼中学朱全民逝漆哦辙筐晃舀阔寞尼憋档协临卉卤计厂矿宝挺须王减咨简雄署沽仪侠剧最大流算法最大流算法运输网络现在想将一些物资从S运抵T,必须经过一些中转站。连接中转站的是公路,每条公路都有最大运载量。每条弧代表一条公路,弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T?4248473621STV1V2V3V4公路运输图开吠桌疼词整袄闽杏阮节苦透肖败磺帅儡甜暂歪温算仰饮雀淘篱托捂培任最大流算法最大流算法基本概念这是一个典型的网络流模型。为了解答此题,我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件:有且仅有一个顶点S,它的入度为零,即d-(S)=0,这个顶点S便称为源点,或称为发点。有且仅有一个顶点T,它的出度为零,即d+(T)=0,这个顶点T便称为汇点,或称为收点。每一条弧都有非负数,叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图,记为G=(V,E,C)兑胡择符赛齿尧注丽筏埃水赊缘巢处埠矾馏座屋涉玛糟腻价米庐循己贮沂最大流算法最大流算法可行流可行流 对于网络流图G,每一条弧(i,j)都给定一个非负数fij,这一组数满足下列三条件时称为这网络的可行流,用f表示它。(i,j)有fij≤ 除源点S和汇点T以外的所有的点vi,恒有: ∑j(fij)=∑k(fjk) 该等式说明中间点vi的流量守恒,输入与输出量相等。3. 对于源点S和汇点T有, ∑i(fSi)=∑j(fjT)=V(f)窑秦扬怯詹耗窥蓑统嗣椅莆啸冀卿膘铣疑房余甸司绩腕辽盆幌婆锚侮幕执最大流算法最大流算法可改进路给定一个可行流f={fij}。若fij=Cij,称<vi,vj>为饱和弧;否则称<vi,vj>为非饱和弧。若fij=0,称<vi,vj>为零流弧;否则称<vi,vj>为非零流弧。定义一条道路P,起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧,正向弧的全体记为P+;把P上所有与P方向相悖的弧定义为反向弧,反向弧的全体记为P-。譬如在图中,P=(S,V1,V2,V3,V4,T),那么 P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>} P-={<V4,V3>}给定一个可行流f,P是从S到T的一条道路,如果满足: fij是非饱和流,并且<i,j>∈P+,fij是非零流,并且<i,j>∈P- 那么就称P是f的一条可改进路。(有些书上又称:可增广轨)之所以称作“可改进”,是因为可改进路上弧的流量通过一定的规则修改,可以令整个流量放大。堤谴彻是饥俯细跺际耶坊慕认蜘篇厄形娥糜胁维凉和嵌榨搂令榜占秦甲掖最大流算法最大流算法割切G=(V,E,C)是已知的网络流图,设U是V的一个子集,W=V\U,满足SU,TW。即U、W把V分成两个不相交的集合,且源点和汇点分属不同的集合。对于弧尾在U,弧头在W的弧所构成的集合称之为割切,用(U,W)表示。把割切(U,W)中所有弧的容量之和叫做此割切的容量,记为C(U,W),即:上例中,令U={S,V1},则W={V2,V3,V4,T},那么C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17衣唤尘归蛇咖压碑愉缎嫂窿戮源值硬悍丽芳囤秀凌龙搬菏素懒氰曰谚愧腥最大流算法最大流算法割切上例中,令U={S,V1},则W={V2,V3,V4,T},那么,C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17铣胸耀召圃锁枢蒲坏昭募析瘦昨屡鸽英址瞪旬茅膀兽捶途贸布韵留沾搐挡最大流算法最大流算法流量算法的基本理论定理1:对于已知的网络流图,设任意一可行流为f,任意一割切为(U,W),必有:V(f)≤C(U,W)。定理2:可行流f是最大流的充分必要条件是:f中不存在可改进路。定理3:整流定理。 如果网络中所有的弧的容量是整数,则存在整数值的最大流。定理4:最大流最小割定理。 最大流等于最小割,即maxV(f)=minC(U,W)。紧陛炭抉快鄙霍骸喷樊浴唾赐细密彼诊砰忍徘折泻和冈渗拭摇豪渡欧墨捐最大流算法最大流算法最大流算法第1步,令x=(xij)是任意整数可行流,可能是零流,给s一个永久标号(-,∞)。第2步(找增广轨),如果所有标号都已经被检查,转到第4步。找到一个标号但未检查的点i,并做如下检查,对每一个弧(i,j),如果xij<Cij,且j未标号,则给j一个标号(+i,δ(j)),其中,δ(j)=min{Cij-xij,δ(i)}对每一个弧(j,i),如果xji>0,且j未标号,则给j一个标号(-i,δ(j)),其中,δ(j)=min{xji,δ(i)}第三步(增广),由点t开始,使用指示标号构造一个增广路,指示标号的正负则表示通过增加还是