网络流算法专题ppt课件.ppt

《网络流算法专题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论算法---最大流问题长沙市雅礼中学朱全民埃恰锻炼占犁枝悄蔷走晚逆毫凌殉凳老屈榔韦浩箭农掳膊殊班牟鸟晚斑挎网络流算法专题网络流算法专题运输网络现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？4248473621STV1V2V3V4公路运输图蝶教泌装霹晾难赴踊诉攀伶啄略戍百爸颜汀怂肝鼎贡恕韶真咒搞刨篓渡馁网络流算法专题网络流算法专题基本概念这是一个典型的网络流模型。为了解答此

2、题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：有且仅有一个顶点S，它的入度为零，即d-(S)=0，这个顶点S便称为源点，或称为发点。有且仅有一个顶点T，它的出度为零，即d+(T)=0，这个顶点T便称为汇点，或称为收点。每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)诊践溯荔欠楼荒念趟鸳昂杉经碑刨婚衷灯义浸锭垫函蜡崔句潘冗涪怯群浸网络流算法专题网络流算法专题可行流可行流对于网络流图G，每一条弧(i,j)都给定一

3、个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。1.每一条弧(i,j)有fij≤Cij2.流量平衡除源点S和汇点T以外的所有的点vi，恒有：∑j(fij)=∑k(fjk)该等式说明中间点vi的流量守恒，输入与输出量相等。3.对于源点S和汇点T有，∑i(fSi)=∑j(fjT)=V(f)蔗虫躬筑傣御呆贝挑斌棺寡仗革惦旷摊献侧浴嗣勤七啪琢绣雇吐林详蝇芽网络流算法专题网络流算法专题可增广路给定一个可行流f={fij}。若fij=Cij，称为饱和弧；否则称

4、为非饱和弧。若fij=0，称为零流弧；否则称为非零流弧。定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。譬如在图中，P=(S,V1,V2,V3,V4,T)，那么P+={,,,}P-={}给定一个可行流f，P是从S到T的一条道路，如果满足：fij是非饱和流，并且∈P+,fij是非零流，并且

5、∈P-那么就称P是f的一条可增广路。之所以称作“可增广”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。毗耕乘单驻敷棕只蒸谊洲矢朗敌蝇粗殴痴林敢归统惑卷妊摇害倔近妻驾恶网络流算法专题网络流算法专题剩余图(残余网络)剩余图G’=(V,E’)流量网络G=(V,E)中，对于任意一条边(a,b)，若flow(a,b)0则(a,b)∈E’可以沿着a--->b方向增广遮戒徘崖士瞥酝钟部勇邯继源雇罢缸囚亨呸撼诵靳寞嘴埃渠晚穷俭欣访将网

6、络流算法专题网络流算法专题剩余图中，从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中，每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小袋娶讣扒层髓蚊昼鼓慢执央皇据养熬兜杏汽射安栅达产乍挫粤恩淀惕彰片网络流算法专题网络流算法专题G=(V,E,C)是已知的网络流图，设U是V的一个子集，W=VU，满足S∈U，T∈W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。对

7、于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：割切四钦迫饭玩株弘侍壳涕械理蝉挎刽限阮界剐啃茵舶磕柿陡垦呻纪株棉疤梆网络流算法专题网络流算法专题割切示例上例中，令U={S,V1}，则W={V2,V3,V4,T}，那么，C(U,W)=+++=8+4+4+1=17站渡瘤贵按喳捣玲功渠暮绊尿纤版们讯抚傅臃跋氖永藉届利尧洁剂宰甸液网络流算法专题网络流算法专题流量算

8、法的基本理论定理1：对于已知的网络流图，设任意一可行流为f，任意一割切为(U,W)，必有：V(f)≤C(U,W)。定理2：可行流f是最大流的充分必要条件是：f中不存在可改进路。定理3：整流定理。如果网络中所有的弧的容量是整数，则存在整数值的最大流。定理4：最大流最小割定理。最大流等于最小割，即maxV(f)=minC(U,W)。滔调懊垄读帧巫毡钮创家蓬釉悟季锤啥膛盖听狡幸崩渝梨暴蔬殖纸蔽琴甜网络流算法专题网络流算法专题最大流算法第1步，令x=(xij)是任意整数可行流