西南交通大学教师赛课总决赛课件-管理运筹学

管理运筹学西南交通大学交通运输学院2023/1/13第十章网络的流§10.2网络最大流算法一学习目的（1）如何判断网络流量达到最大？（2）如何增加网络的流量？二学习内容三学习总结相关知识回顾相关概念基础概念核心概念§10.2.2寻找增流链寻找增流链2023/1/132第十章网络的流

（1）设f为G上一个流，若存在e∈E，f(e)=C(e),称边e为f饱和边；（2）若存在f(e)<C(e)，称边e为f不饱和边；（3）若f(e)>0，称边e为f正边;若f(e)=0，称边e为f零边。（4）设Q=x，∙∙∙，u，v，∙∙∙，t为f的一条初等链，则：

G中u到v的有向边(u,v)，称边(u,v)为Q的前向边；G中v到u的有向边(v,u)，称边(v,u)为Q的后向边。（一）基本概念一相关概念2023/1/133第十章网络的流若f为G上的流，对e∈E(Q)，令：当l(Q)=0时，称Q为f饱和链；当l(Q)>0时，称Q为f不饱和链。（二）核心概念（1）饱和链及不饱和链l(e)、l(Q)隐含的意义是什么？饱和链、不饱和链的性质是什么？令2023/1/134(180,150)(60,50)(40,20)(120,30)(150,130)(70,70)(70,50)(130,100)(240,230)示例(150,150)v3v1v2(100,100)(120,120)x2x1xy2y1y(200,200)取链Q1=xx2v2x1v1，边(x,x2),(x2,v2)和(x1,v1)为Q1的前向边，L(x,x2)=10,L(x2,v2)=30,L(x1,v1)=0；边(v2,x1)为Q1的后向边，L(v2,x1)=50。则L(Q1)=0，Q1为饱和链。取链Q2=x2v3y2v1y1y，边(x2,v3),(v3,y2),(v1,y1)和(y1,y)为Q2前向边，L(x2,v3)=20，L(v3,y2)=90，L(v1,y1)=10，L(y1,y)=30；边(y2,v1)为Q2后向边，L(y2,v1)=20。则L(Q2)=10，Q2为不饱和链。第十章网络的流2023/1/135(240,230)(130,100)(150,130)(70,70)(150,150)(120,30)(40,20)(60,50)(70,50)v3v1v2(100,100)(120,120)x2x1xy2y1y(180,150)(200,200)（2）增流链一条从源x到汇y的流f不饱和链称为f增流链。增流链与不饱和链的区别是什么？Q=xx2+Q2即为增流链第十章网络的流2023/1/136（三）增流链的作用对网络G中存在一条流f的增流链Q，给出调整公式：利用调整公式可以把不饱和的增流链流量增加成一个新流，即将增流链调整为饱和链。这里把l(Q)称为增流链Q的调整量。第十章网络的流2023/1/1371、标号未查视边（u，v）的顶点v，的标号方式为：（u，边的方向，l(v)）标号点的前个顶点v为终点用+表示v为始点用-表示2、进行查视，即顶点v能否长枝条件为：（1）边e=(v,z)为前向边，f(e)<C(e)。（2）边e=(v,z)为后向边，f(e)>0。4、不断循环直至不能长枝。3、若顶点z能够长枝，对z进行标号。第十章网络的流二寻找增流链v为终点：l(v)=min{l(u),C(u,v)-f(u,v)}v为始点：l(v)=min{l(u),f(u,v)}2023/1/138(1,0)x1示例xyx2x3v1v2v4v3y1y2y3(5,0)(4,3)(3,3)(8,6)(8,3)(4,1)(7,5)(8,2)(2,2)(2,1)(7,0)(4,1)(4,2)(2,2)(1,1)(5,3)(3,2)(4,2)(12,4)(8,4)(12,5)(11,3)(11,3)(11,7)(0,+,+∞)(x,+,8)(x1,+,3)(v1,-,1)(v4,+,1)(y3,+,1)第十章网络的流2023/1/139管理运筹学谢谢2023/1/1310前面知识回顾图G={V,E}网络G={V,E,C,F,X,Y}G={V,E,W}容量约束条件0≤f(e)≤C(e)，任意e∈E；流量守恒条件f+(v)=f-(v)，任意v∈I；流量分配遵从的条件定理流f为G的最大流的充要条件为G中不存在f增流链G={V,E,C,F,W,X,Y}2023/1/13115,27,48,37,3985,37,387第十章网络的流4,27,25,36,58,2v4777,28,25,34,26,5v488,34,26,5v48xyxy2023/1/1312l=4-1=3l=5-3=2l=6-2=4l=5-3=2l=6-2=4l=6-2=4第十章网络的流l(Q1)=min(4)=46,2Q1:V1V26,25,3Q2:V1V2V3l(Q2)=min(4,2)=2l(Q3)=min(4,2,3)=26,2Q3:V1V25,3V34,1V4l(Q3)=min(l(Q2),3)=2l(v2)=4l(v3)=2l(v4)=2l(v3)=2前向边：l(v)=min{l(u),C(u,v)-f(u,v)}后向边：l(v)=min{l(u),f(u,v)}l(v4)=2l(Q3)=min(l(v3),3)=2Q4:6,2V1V25,3V34,1V4V53,1l(Q4)=min(l(v4),1)=1l(v5)=1l(v2)