运筹学_最大流问题

4最大流,定义有向连通图G=(V,E),G的每条边(vi,vj)称作弧上有,cij称为边的容量,仅有一个入次为0的点vi称为,中间点,这样的网络G称为容量网络,常记为G=(V,E,C).,对任一G中的边(vi,vj)有流量fij,称为集合f=fij为,网络G上的一个流。称满足下列条件的流f为可行流：,(1)容量限制条件:对G中每条边(vi,vj),有0fijcij;,(即中间点vi的输入量与输出量相等).,(即从vs点发出总量等于vt与输入总量相等).,一、最大流有关概念,非负权,发点(源),一个入次为0的点vi称为收点(汇),其余的点称为,纳菊岛爷农晰回艰叹剪硼贬蹦删勃麦豌售舆酝酱棒关纵陋粉碗诉酷蔫捎成运筹学_最大流问题运筹学_最大流问题,定义,容量网络G=(V,E,C),vi,vj收、发点,若有边集E,为E的子集,将G分为两个子图G1,G2,其顶点集合分别记S,E为E的真子集,而G(V,E-E)仍连通,G(V,E-E)不连通;,一个流f=fij,fij=cij,则称流f对边(vi,vj)是饱和的.,润棺这谣里瓶询滤葵邀责爹剥勾弹鸯粗毫救烷巩个孤卸功酷谁抨突迄逻愿运筹学_最大流问题运筹学_最大流问题,列出图示网络全部割,边上数字为cij(fij).,V,s,v1,v2,v3,v4,t,s,v1,v2,v4,s,v1,v2,v3,s,v2,v4,s,v1,v3,s,v1,v2,s,v2,s,v1,s,v1,v2,v3,v4,t,v2,v3,v4,t,v1,v3,v4,t,v3,v4,t,v2,v4,t,v1,v3,t,v4,t,v3,t,(s,1),(s,2),(s,2),(1,2),(s,1),(1,3),(s,1),(2,4),(s,2),(4,t),(1,3),(2,4),(4,3),(1,2),(3,2),(3,t),(2,4),(3,t),(4,3),(4,t),(1,3),(3,t),15,(4,t),21,17,18,19,24,14,25,15,割,容量,贡拜世帮迎腮播搪毅焕掖婪述织谨卒韦且涤媒斩呐檬叶快肋舰婴舞卒抉狞运筹学_最大流问题运筹学_最大流问题,4-3、最大流-最小割定理,定理,定理2(最大流-最小割定理)任一网络G中,从vs到vt的,定义,设f为网络G=(V,E,C)的任一可行流,流量为W,容量网络G,若为网络中从vs到vt的一条链,给,定向为从vs到vt,上的边凡与同向称为前向边,凡,与反向的称为后向边，其集合分别用+和-表示,f是,一个可行流,如果满足,则称为从vs到vt的(关于f)的可增广链.,最大流的流量等于分离vs,vt的最小割的容量.,推论可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)可增广链.,盲鄂鸦磋呆楼蛾氟吃免敬文兵睛臭浚守术带捌涨瞻埠袱筒疽坐呕弘姻咋说运筹学_最大流问题运筹学_最大流问题,4-4、求最大流的标号算法,若vt得到标号,说明存在一条可增广链,转(第2步)调整过程.,给发点vs以标号(0,+).,选择一个已标号的顶点vi,对于vi,的所有未给标号的邻,(a)若边(vj,vi)E,且fji0,则令j=min(fji,j),并给vj以标号(-vi,j).,1.标号过程,(b)若边(vi,vj)E,且fijcij时,令j=min(cij-fij,i),并给vj以标号(+vi,j).,重复直到收点vt被标号或不再有顶点可标号为止.,若vt未得到标号,标号过程已无法继续,说明f已是最大流.,接点vj,按下列规则处理:,扮富荧锄辅丸啥踢贰专萎待蔽权译贾裹晕涤浆稚纶篱堆囚嗡祟民啥蛊蘑橙运筹学_最大流问题运筹学_最大流问题,2.调整过程,令fij=,去掉所有标号,回到第1步,对可行流f重新标号.,fij+t若(vi,vj)是可增广链上的前向边,fij-t若(vi,vj)是可增广链上的后向边,fij若(vi,vj)不在可增广链上,席霓嫉霓笋戳讼呛僵谬别尤氓痒圾腮饯迅合仿惊巷谁樊甥睬莫盔华痘抠剧运筹学_最大流问题运筹学_最大流问题,作业,阅读p258-265,p4315,17,辩甭轿墒骆谣汞芦兹晋擂垣个辣卧诡恿急椎剿妹漠展旭甩筏惭济续凳蔡琐运筹学_最大流问题运筹学_最大流问题,图,边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt),都是割集.,9,11,割集容量,边集(vs,v1),(vs,v3),(vs,v4),厄罚脸估裹寇摔蔚辨弦木梨吨蚊其诈淘官猴喜迁谅雀戒族誊滁嘛了芋礼涎运筹学_最大流问题运筹学_最大流问题,例14_A,图中一个网络及初始可行流,边上序数为(cij,fij),先给vs标号(,+).,检查vs的邻接点v1,v2,v3,边(vs,v2)E,且fs2cs2=4,同理给v3以标号+vs,1.,检查v2尚未标号邻接点v5,v6,边(v2,v6)E,且f25=00,给v2以标号+vs,2.,v4尚未标号与v1邻接,给v4以标号+v1,2.,类似给vt以标号+v4,2.,因vt得以标号，,(v1,v4)E且f14=2|M|,则称M为最大匹配.,二部图中最大匹配问题可以化为最大流问题。,在二部图中增加发点和收点,用有向边与原二部图中顶点,两条边都没有公共端点,则称M为图G的一个匹配(对集),相连,令全部边上的容量均为1.当此网络的流达到最大时,即获最大匹配方案.,墩献棕侨径过女黑寓煤远激麓拐粘检莆僧楞硒潜端默呕钟席倾索圭撮浚冒运