Chap图与网络分析实用PPT课件

1、Copyrights 2006 - powered by nerdpal HIT 最短路问题: 从给定的网络图中找出某一点到其它点的最短距离 公认的求最短路径问题的较好的算法是由E.W.Dijkstra(狄克斯屈拉)于1959年给出的标号法最短路问题第1页/共45页Copyrights 2006 - powered by nerdpal HITV1V5V6V2V3V75727241360226V4567710Dijkstra标号法本页播放时隐藏,保留第2页/共45页Copyrights 2006 - powered by nerdpal HITV1V5V6V2V3V75727241360226

2、V4Dijkstra标号法第3页/共45页Copyrights 2006 - powered by nerdpal HITV1V5V6V2V3V75727241360226V45Dijkstra标号法第4页/共45页Copyrights 2006 - powered by nerdpal HITV1V5V6V2V3V75727241360226V456Dijkstra标号法第5页/共45页Copyrights 2006 - powered by nerdpal HITV1V5V6V2V3V75727241360226V45677Dijkstra标号法第6页/共45页Copyrights 200

3、6 - powered by nerdpal HITV1V5V6V2V3V75727241360226V4567710Dijkstra标号法第7页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra标号法有向图本页播放时隐藏,保留第8页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2V3V7577241360226V4Dijkstra标号法有向图第9页/共45页Copyrights 2006 - powered

4、by nerdpal HIT2V1V5V6V2V3V7577241360226V45Dijkstra标号法有向图第10页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2V3V7577241360226V459Dijkstra标号法有向图第11页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2V3V7577241360226V45119Dijkstra标号法有向图第12页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2

5、V3V7577241360226V4511129Dijkstra标号法有向图第13页/共45页Copyrights 2006 - powered by nerdpal HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra标号法有向图第14页/共45页Copyrights 2006 - powered by nerdpal HIT最短路问题的数学模型第15页/共45页p 图的基本概念与模型p 树图和图的最小生成树p 最短路问题p 中国邮递员问题p 网络最大流运筹学基础及应用之图与网络分析第16页/共45页Copyrights 2006 - powered

6、by nerdpal HIT一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程最短？V1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题类似于欧拉回路欧拉回路第17页/共45页Copyrights 2006 - powered by nerdpal HITKonigsberg七桥问题欧拉回路欧拉图ACBDABCD第18页/共45页Copyrights 2006 - powered by nerdpal HITa)是欧拉图；b)不是欧拉图，但存在欧拉回路；c)即不是欧拉图，也不存在欧拉回路。例(

7、a)(b)(b)(c)(c)第19页/共45页Copyrights 2006 - powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题每条边上最多重复一次在图G的每个回路上，有重复的边的长度不超过回路总长的一半欧拉图将奇点两两相连，变成偶点第20页/共45页Copyrights 2006 - powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题在图G的每个回路上，有重复的边的长度不超过回路总长的一半第

8、21页/共45页Copyrights 2006 - powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题第22页/共45页p 图的基本概念与模型p 树图和图的最小生成树p 最短路问题p 中国邮递员问题p 网络最大流运筹学基础及应用之图与网络分析第23页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流一 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。 而网络系统的最大流问题是图与

9、网络流理论中的最优化问题，它对于解决生产实际问题起着十分重要的作用。第24页/共45页Copyrights 2006 - powered by nerdpal HIT每条弧旁边的权就是对应的容量(最大通过能力)。要求指定一个产品运输方案，使得从st的货运量最大，这是寻求网络系统的最大流问题，即从发点s到收点t允许通过的最大流量。tv3v2v1v4s1069879552Cij5 网络最大流第25页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流二 基本概念 定义 设一个加权有向图D(V,A)，在V中指定一个发点s和一个收点t，其他的点叫做中

10、间点。对于D中的弧(vi,vj)A，都有一个权 cij 叫做弧的容量。这样的图D称做一个网络系统，简称网络，记做 D(V,A,C)。 网络D上的流，是指加在弧集合A上的一组负载量,记作 f (vi,vj) ,或 fij. 若网络上所有的 fij=0，称为零流。第26页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流 该图给出了网络上的一个流（运输方案）,每一个弧上的流量 fij 就是运输量，例如 fs1=8，fs2=5，f13=4 等等tv3v2v1v4s(8)(1)(4)(8)(5)(9)(5)(4)(0)fij第27页/共45页Cop

11、yrights 2006 - powered by nerdpal HIT5 网络最大流网络系统上流流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的净流量=0，即流入量-流出量=0；(3)每一条弧上的流量不能超过它的最大通过能力（即容量）。第28页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流定义 网络上的一个流 f 称作可行流，若 f 满足以下条件：（1）容量条件：对于每一个弧（vi,vj）A，有0 fij cij（2）平衡条件： 对于发点 s ，有 fsj - fjs = v(f) 对于收点 t ，有 ft

12、j - fjt = - v(f) 对于中间点，有 fij - fji = 0v(f) 表示可行流的流量。第29页/共45页Copyrights 2006 - powered by nerdpal HIT根据可行流的定义,得到最大流的数学模型: max,. .,0,0, ( , ).ffijjifj Vj Vijijvvisstffvitis tfci jA 5 网络最大流第30页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流 任意一个网络都存在可行流。如零流v(f)=0v(f)=0,就满足可行流的条件。 网络系统中最大流问题就是在给定的

13、网络上寻求一个可行流 f f ,其流量 v(f)v(f) 达到最大值。 设流f=ff=fijij 是网络D上的一个可行流，f fijij=c=cijij的弧称为饱和弧；f fijijc0 0 的弧为非零流弧，f fijij=0=0的弧为零流弧。第31页/共45页Copyrights 2006 - powered by nerdpal HIT割是指将网络中的发点和收点分割开,并使st的流中断的一组弧的集合. K将网络上的点分割成V和V，sV, tV, 称弧集（V,V）=(v1,v3),(v2,v4) 是分离s和t的割.注意:弧(v3,v2)即使不割断,从st的流仍然中断.Ktv3v2v1v4s1

14、0(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij (fij)第32页/共45页Copyrights 2006 - powered by nerdpal HIT 将割 中所有弧的容量之和称作割的容量，记作 ,即( , )V V( , )cV V(, ) ( , )( , )( , )ijijV VcV Vc v v=Ktv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij (fij)第33页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流结论: 在网络D中,任何一个

15、可行流 f 的流量 v(f) 都小于或等于这个网络中任何一个割(V,V) 的容量. 设是网络D中连接发点 s 和收点 t 的一条链。定义链的方向是从st，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，记作+ +; ;二是弧的方向与链的方向相反，叫做后向弧，记作- -.第34页/共45页Copyrights 2006 - powered by nerdpal HIT饱和弧:(s,v1),(v2,v4),(v3,t); 其他的弧都是非饱和弧; (v3,v2)是零流弧.如图，在链（s,v1,v2,v3,v4,t)中，+=(s,v1),(v1,v2),(v4,t), - =(v3,

16、v2),(v4,v3).5 网络最大流tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij (fij)第35页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流增广链，如果链满足以下条件：1在弧（vi,vj）+ 上，有 0 = fij cij ，即+ 中的每一条弧是非饱和弧。2在弧（vi,vj）- 上，有 0 fij = cij ，即- 中的每一条弧是非零流弧。第36页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流如图，链=（s,v2,

17、v1,v3,v4,t）就是一条增广链。tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij (fij)第37页/共45页Copyrights 2006 - powered by nerdpal HIT当有增广链存在时,令 ,min,iiicfforffor 再令 此时仍是可行流,流量比增大了.因此当网络图中没有增广链时,的流才不会进一步增大. 第38页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流 定理1 网络中的一个可行流 f* 是最大流当且仅 当不存在关于 f* 的增广链。 定理2 在

18、网络中 st 的最大流量等于最小割的容量。 定理1实际上提供了寻求网络系统最大流的方法：如果网络D中有一个可行流 f ，只要判断网络是否存在关于可行流 f 的增广链 。 如果没有增广链，那么 f 一定是最大流。 如有增广链，可以按照定理2，不断增大可行流f的流量，最终可以得到一个最大流。第39页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流三标号法 从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。 用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V

19、1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。第40页/共45页Copyrights 2006 - powered by nerdpal HIT5 网络最大流1标号过程 在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了用来确定增广链上的调整量。 标号过程开始，先给vs标号（0，+）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：第41页/共45