第四章图与网络优秀课件.ppt

《第四章图与网络优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章图与网络优秀课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章图与网络第四章图与网络第1页，本讲稿共55页图和网络图和网络图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。图论的历史最早可以追溯到1736年瑞士数学家E.Euler解决著名的哥尼斯堡七桥问题。第2页，本讲稿共55页哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。第3页，本讲稿共55页哥尼

2、斯堡七桥问题哥尼斯堡七桥问题第4页，本讲稿共55页图与网络的基本概念图与网络的基本概念V1V2V3de2e3e6e4e5V4V5e1V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5G=(V,E)端点；关联边端点；关联边无向边；有向边（弧）无向边；有向边（弧）环（自回路）环（自回路）多重边多重边简单图；多重图简单图；多重图悬挂点悬挂点网络网络第5页，本讲稿共55页连通图连通图 点边序列；点边交替序列；点边序列；点边交替序列；点边序列；点边交替序列；点边序列；点边交替序列；在点边交替系列中，顺序排列的任意两条边均为相在点边交替系列中，顺序排列的任意两条边均为相在点边交替系列中，顺序

3、排列的任意两条边均为相在点边交替系列中，顺序排列的任意两条边均为相邻边，则称该点边交替序列为链；邻边，则称该点边交替序列为链；邻边，则称该点边交替序列为链；邻边，则称该点边交替序列为链；点边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链 圈（回路）圈（回路）圈（回路）圈（回路）V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10第6页，本讲稿共55页链、路链、路(1)(1)第7页，本讲稿共55页链、路链、路(2)(2)v1a1v2a2v3a7v4v5a4a3a8a9路：在

4、一条链中，每条弧的方向与序列的走向一致，则称该链为路。回路：起点和终点重合与同一节点的路。回路与圈的区别是所有弧的方向一致。第8页，本讲稿共55页图、子图、支撑子图图、子图、支撑子图第9页，本讲稿共55页树树一个无圈的连通图称为树树。第10页，本讲稿共55页树树例：五个城市之间架设电话线。要求任何两个城市都可以相互通话（允许通过其他城市），并且电话线的根数最少。V2V1V3V4V5第11页，本讲稿共55页图的基本概念小结图的基本概念小结边、弧无向图、有向图无向图:(1)端点、相邻、关联边(2)环、多重边、简单图 (3)悬挂点 (4)链、圈、初等链 (5)连通图、支撑子图有向图:(1)始点、终点

5、 (2)路、回路第12页，本讲稿共55页割集割集v2v1v3v4v5v6abcdefghkv1v2v6v3v4v5在一个连通图中割集是一些边的集合，从G中移去这些边，则G不连通，并且不存在这些边的真子集使图不连通第13页，本讲稿共55页最短路问题最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权 lij(lij=表示vi,vj之间无边)，vs,vt为图中任意两点，求一条路，使它是从vs到vt的所有路中总权数最小的路。第14页，本讲稿共55页最短路问题最短路问题123434563234221第15页，本讲稿共55页Edsger Wybe DijkstraEdsger Wybe Dij

6、kstra中文名：艾兹格迪科斯彻 家乡：荷兰 出生年月：1930年5月11日 去世年月：2002年8月6日 成就：1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖 1989年ACM SIGCSE计算机科学教育教学杰出贡献奖 2002年ACM PODC最具影响力论文奖 第16页，本讲稿共55页D D氏标号法氏标号法思路：从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。条件：网络中所有的弧权为非负。第17页，本讲稿共55页开始给发点标上P(Vs)=0,其余节点标上临时标号T(Vj)=，j1;设节点Vi是刚得到的P类标号，把与节点Vi有弧直接相连而又属于T类标号的各节点Vj的标号

7、改为：T(Vj)=minT(Vj),P(Vj)+dij在T类标号中选标号最小的节点Vj0，并把它的临时标号T(Vj0)改为P(Vj0)，若终点获得P类标号，则停止，否则转上一步。D D氏标号法步骤氏标号法步骤第18页，本讲稿共55页最短路问题最短路问题v1v2v7v5v4171344452572v3v6第19页，本讲稿共55页最短路求解最短路求解图中()内的数表示P标号，内的数表示T标号。v1(0)v2v7v5v411344452572v3v67 (1)首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+；第20页，本讲稿共55页最短路算法最短路算法 (2)由于弧(v1,v2

8、)、(v1,v3)、(v1,v4)属于D，且v2、v3、v4为T标号，所以修改这三个点的标号：T(v2)=minT(v2),P(v1)+12=min,0+4=4T(v3)=minT(v3),P(v1)+13=min,0+2=2 T(v4)=minT(v4),P(v1)+14=min,0+5=5v1(0)v2v7v5v411344452572v32v6457第21页，本讲稿共55页最短路算法最短路算法 (3)比较所有T标号，T(v3)最小，故令P(v3)=2v1(0)v2v7v5v411344452572v3(2)v6457第22页，本讲稿共55页最短路算法最短路算法 (4)v3为刚得到P标号的

9、点，考察弧(v3,v4)，(v3,v6)的端点v4,v6T(v4)=minT(v4),P(v3)+34=min5,2+2=4T(v6)=minT(v6),P(v3)+36=min,2+7=9v1(0)v2v7v5v411344452572v3(2)v6457第23页，本讲稿共55页最短路算法最短路算法 (5)比较所有T标号，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4v1(0)v2v7v5v411344452572v3(2)v64497第24页，本讲稿共55页最短路算法最短路算法v1(0)v2v7v5v411344452572v3(2)v6(4)(4)97第25页，本讲稿共55

10、页最短路算法最短路算法 (6)v2,v4为刚得到P标号的点,考察弧(v2,v5)，(v4,v5)，(v4,v6)的端点v5,v6 T(v5)=minT(v5),P(v4)+45,P(v2)+25 =min,4+3,4+4=7 T(v6)=minT(v6),P(v4)+46=min9,4+4=8v1(0)v2v7v5v411344452572(4)(4)877v3(2)v6第26页，本讲稿共55页最短路算法最短路算法 (7)比较所有T标号，T(v5)最小，所以令P(v5)=7v1(0)v2v7v5v411344452572(4)(4)(7)8v3(2)v67第27页，本讲稿共55页最短路算法最短

11、路算法v1(0)v2v7v5v411344452572(4)(4)(7)148v3(2)v6 (8)v5为刚得到P标号的点，考察弧(v5,v6)，(v5,v7)的端点v6,v7 T(v6)=minT(v6),P(v5)+56=min8,7+1=8 T(v7)=minT(v7),P(v5)+57=min,7+7=147第28页，本讲稿共55页最短路算法最短路算法 (9)比较所有T标号，T(v6)最小，所以令P(v6)=8v1(0)v2v7v5v411344452572(4)(4)(7)14(8)v3(2)v67第29页，本讲稿共55页最短路算法最短路算法 (10)v6为刚得到P标号的点，考察弧(

12、v6,v7)的端点v7 T(v7)=minT(v7),P(v6)+67=min14,8+5=13v1(0)v2v7v5v411344452572(4)(4)(7)13(8)v3(2)v67第30页，本讲稿共55页最短路算法最短路算法 (11)只有一个T标号T(v7)，令P(v7)=13，停止。v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67 计算结果见上图，v1到v7的最短路为：同时得到v1到其余各点的最短路。第31页，本讲稿共55页应用举例应用举例例：例：(设备更新问题设备更新问题)某企业在四年内都要使用某种某企业在四年内都要使用某种设备，在每

13、年年初作出是购买新设备还是继续使用设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置费；若旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：的设备的维修费用估计为：年份1 12 23 34 4 年初购价1010111112121313 维修费用2 24 47 71414第32页，本讲稿共55页应用举例应用举例问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和

14、维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。第33页，本讲稿共55页最短路求法（最短路求法（2 2）构造长度矩阵L计算 其中第34页，本讲稿共55页最短路求法（最短路求法（2 2）长度矩阵第35页，本讲稿共55页最短路求法（最短路求法（2 2）表示vi到vj两步中距离最短的一条表示vi到vj两步不能到达第36页，本讲稿共55页最短路求法（最短路求法（2 2）第37页，本讲稿共55页最短路求法（最短路求法（2 2）第38页，本讲稿共55页最短路求法（最短路求法（2 2）第39页，本讲稿共55页最短路求法（最短路求法（2 2）求任意两点最短距离均为mxn矩阵第40

15、页，本讲稿共55页最短路求法（最短路求法（2 2）矩阵中元素为两点间最顿距离第41页，本讲稿共55页最大流引入最大流引入输油管道网，如何安排各管道的输油量，才能使从vs到vt总油量最大？第42页，本讲稿共55页最大流问题最大流问题管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量；如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。第43页，本讲稿共55页基本概念基本概念容量：G=(V,E)，每条边上有非负数cij称为边的容量；发点（源），收点（汇），中间点；对G中的边（vi,vj）有流量fij,称集合f=fij为网络G上的流；第44页，本讲稿共

16、55页基本概念基本概念可行流容量限制：对G中的每条边（vi,vj）,有平衡条件：对中间点vi,有 对收点、发点有所谓最大流问题，就是在容量网络中，寻找流量最大的可行流。当fij=cij,则称流对边（vi,vj）是饱和的。第45页，本讲稿共55页最大流最小割最大流最小割第46页，本讲稿共55页最大流最小割最大流最小割在容量网络中割集是由vs到vt的必经之路，无论拿掉哪个割集，vs到vt便不再相通，所以任何一个可行流的流量不会超过任一割集的容量；定理：任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。第47页，本讲稿共55页最大流算法最大流算法增广链（路）容量网络G，为从

17、vs到vt的一条链，给定向为从vs到vt，与同向的边称为前向边，记为 与反向称为后向边，记为 f 为可行流，如果满足：则称记为为从vs到vt的一条增广链。第48页，本讲稿共55页最大流算法最大流算法标号算法标号算法思路：找出一条从发点输送正流到收点的链增广链，利用这条路把尽可能多的流从发点送到收点，重复这个过程，直到再也找不出增广链为止，这时网络上的流就是最大流。增广链：从发点到收点的链，前向弧的流量小于容量，后向弧的流量大于零。第49页，本讲稿共55页第一第一 标号过程标号过程可扩充量标号正向(Vi,Vj)反向(Vj,Vi)第50页，本讲稿共55页第二第二 调整过程调整过程第51页，本讲稿共55页最大流问题最大流问题1 1VsV2V13,35,1V4V3Vt4,32,25,32,13,01,11,1c,f第52页，本讲稿共55页最大流问题最大流问题2 2VsV2V13,35,2V4V3Vt4,32,25,32,23,01,01,0第53页，本讲稿共55页习题习题4.24.2用标号法求图示的最短路第54页，本讲稿共55页习题习题4.34.3Va,Vb两城市公路网。弧上的数字为每段的距离（里数），求Va,Vb间的最短路。第55页，本讲稿共55页