《第四章图与网络精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章图与网络精选文档.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章图与网络第四章图与网络本讲稿第一页，共五十五页图和网络图和网络图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。图论的历史最早可以追溯到1736年瑞士数学家E.Euler解决著名的哥尼斯堡七桥问题。本讲稿第二页，共五十五页哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。本讲稿第三页，共五十五
2、页哥尼斯堡七桥问题哥尼斯堡七桥问题本讲稿第四页，共五十五页图与网络的基本概念图与网络的基本概念V1V2V3de2e3e6e4e5V4V5e1V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5G=(V,E)端点；关联边端点；关联边无向边；有向边（弧）无向边；有向边（弧）环（自回路）环（自回路）多重边多重边简单图；多重图简单图；多重图悬挂点悬挂点网络网络本讲稿第五页，共五十五页连通图连通图点边序列；点边交替序列；点边序列；点边交替序列；在点边交替系列中，顺序排列的任意两条边均为相在点边交替系列中，顺序排列的任意两条边均为相邻边，则称该点边交替序列为链；邻边，则称该点边交替序列为链；点
3、边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链点边列中没有重复的点和重复边者称为初等链 圈（回路）圈（回路）圈（回路）圈（回路）V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10本讲稿第六页，共五十五页链、路链、路(1)(1)本讲稿第七页，共五十五页链、路链、路(2)(2)v1a1v2a2v3a7v4v5a4a3a8a9路：在一条链中，每条弧的方向与序列的走向一致，则称该链为路。回路：起点和终点重合与同一节点的路。回路与圈的区别是所有弧的方向一致。本讲稿第八页，共五十五页图、子图、支撑子图图、子图、支撑子图
4、本讲稿第九页，共五十五页树树一个无圈的连通图称为树树。本讲稿第十页，共五十五页树树例：五个城市之间架设电话线。要求任何两个城市都可以相互通话（允许通过其他城市），并且电话线的根数最少。V2V1V3V4V5本讲稿第十一页，共五十五页图的基本概念小结图的基本概念小结边、弧无向图、有向图无向图:(1)端点、相邻、关联边(2)环、多重边、简单图 (3)悬挂点 (4)链、圈、初等链 (5)连通图、支撑子图有向图:(1)始点、终点 (2)路、回路本讲稿第十二页，共五十五页割集割集v2v1v3v4v5v6abcdefghkv1v2v6v3v4v5在一个连通图中割集是一些边的集合，从G中移去这些边，则G不连通
5、，并且不存在这些边的真子集使图不连通本讲稿第十三页，共五十五页最短路问题最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权 lij(lij=表示vi,vj之间无边)，vs,vt为图中任意两点，求一条路，使它是从vs到vt的所有路中总权数最小的路。本讲稿第十四页，共五十五页最短路问题最短路问题123434563234221本讲稿第十五页，共五十五页Edsger Wybe DijkstraEdsger Wybe Dijkstra中文名：艾兹格迪科斯彻 家乡：荷兰 出生年月：1930年5月11日 去世年月：2002年8月6日 成就：1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖
6、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖 2002年ACM PODC最具影响力论文奖 本讲稿第十六页，共五十五页D D氏标号法氏标号法思路：从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。条件：网络中所有的弧权为非负。本讲稿第十七页，共五十五页开始给发点标上P(Vs)=0,其余节点标上临时标号T(Vj)=，j1;设节点Vi是刚得到的P类标号，把与节点Vi有弧直接相连而又属于T类标号的各节点Vj的标号改为：T(Vj)=minT(Vj),P(Vj)+dij在T类标号中选标号最小的节点Vj0，并把它的临时标号T(Vj0)改为P(Vj0)，若终点获得P类标号，则停止，否
7、则转上一步。D D氏标号法步骤氏标号法步骤本讲稿第十八页，共五十五页最短路问题最短路问题v1v2v7v5v4171344452572v3v6本讲稿第十九页，共五十五页最短路求解最短路求解图中()内的数表示P标号，内的数表示T标号。v1(0)v2v7v5v411344452572v3v67 (1)首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+；本讲稿第二十页，共五十五页最短路算法最短路算法 (2)由于弧(v1,v2)、(v1,v3)、(v1,v4)属于D，且v2、v3、v4为T标号，所以修改这三个点的标号：T(v2)=minT(v2),P(v1)+12=min,0+4=4
8、T(v3)=minT(v3),P(v1)+13=min,0+2=2 T(v4)=minT(v4),P(v1)+14=min,0+5=5v1(0)v2v7v5v411344452572v32v6457本讲稿第二十一页，共五十五页最短路算法最短路算法 (3)比较所有T标号，T(v3)最小，故令P(v3)=2v1(0)v2v7v5v411344452572v3(2)v6457本讲稿第二十二页，共五十五页最短路算法最短路算法 (4)v3为刚得到P标号的点，考察弧(v3,v4)，(v3,v6)的端点v4,v6T(v4)=minT(v4),P(v3)+34=min5,2+2=4T(v6)=minT(v6)
9、,P(v3)+36=min,2+7=9v1(0)v2v7v5v411344452572v3(2)v6457本讲稿第二十三页，共五十五页最短路算法最短路算法 (5)比较所有T标号，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4v1(0)v2v7v5v411344452572v3(2)v64497本讲稿第二十四页，共五十五页最短路算法最短路算法v1(0)v2v7v5v411344452572v3(2)v6(4)(4)97本讲稿第二十五页，共五十五页最短路算法最短路算法 (6)v2,v4为刚得到P标号的点,考察弧(v2,v5)，(v4,v5)，(v4,v6)的端点v5,v6 T(v5)
10、=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本讲稿第二十六页，共五十五页最短路算法最短路算法 (7)比较所有T标号，T(v5)最小，所以令P(v5)=7v1(0)v2v7v5v411344452572(4)(4)(7)8v3(2)v67本讲稿第二十七页，共五十五页最短路算法最短路算法v1(0)v2v7v5v411344452572(4)(4)(7)148v3(2)v6 (8)v5为刚得到P标号的点，考察弧(
11、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本讲稿第二十八页，共五十五页最短路算法最短路算法 (9)比较所有T标号，T(v6)最小，所以令P(v6)=8v1(0)v2v7v5v411344452572(4)(4)(7)14(8)v3(2)v67本讲稿第二十九页，共五十五页最短路算法最短路算法 (10)v6为刚得到P标号的点，考察弧(v6,v7)的端点v7 T(v7)=minT(v7),P(v6)+67=min14,8+5=13v1(0)v2v7v5v41
12、1344452572(4)(4)(7)13(8)v3(2)v67本讲稿第三十页，共五十五页最短路算法最短路算法 (11)只有一个T标号T(v7)，令P(v7)=13，停止。v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67 计算结果见上图，v1到v7的最短路为：同时得到v1到其余各点的最短路。本讲稿第三十一页，共五十五页应用举例应用举例例：例：(设备更新问题设备更新问题)某企业在四年内都要使用某种设某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续使用旧设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购
13、置费；若继续使备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：修费用估计为：年份1 12 23 34 4 年初购价1010111112121313 维修费用2 24 47 71414本讲稿第三十二页，共五十五页应用举例应用举例问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。本讲稿第三十三页，共五十五页最短路求
14、法（最短路求法（2 2）构造长度矩阵L计算 其中本讲稿第三十四页，共五十五页最短路求法（最短路求法（2 2）长度矩阵本讲稿第三十五页，共五十五页最短路求法（最短路求法（2 2）表示vi到vj两步中距离最短的一条表示vi到vj两步不能到达本讲稿第三十六页，共五十五页最短路求法（最短路求法（2 2）本讲稿第三十七页，共五十五页最短路求法（最短路求法（2 2）本讲稿第三十八页，共五十五页最短路求法（最短路求法（2 2）本讲稿第三十九页，共五十五页最短路求法（最短路求法（2 2）求任意两点最短距离均为mxn矩阵本讲稿第四十页，共五十五页最短路求法（最短路求法（2 2）矩阵中元素为两点间最顿距离本讲稿第
15、四十一页，共五十五页最大流引入最大流引入输油管道网，如何安排各管道的输油量，才能使从vs到vt总油量最大？本讲稿第四十二页，共五十五页最大流问题最大流问题管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量；如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。本讲稿第四十三页，共五十五页基本概念基本概念容量：G=(V,E)，每条边上有非负数cij称为边的容量；发点（源），收点（汇），中间点；对G中的边（vi,vj）有流量fij,称集合f=fij为网络G上的流；本讲稿第四十四页，共五十五页基本概念基本概念可行流容量限制：对G中的每条边（vi,vj）,
16、有平衡条件：对中间点vi,有 对收点、发点有所谓最大流问题，就是在容量网络中，寻找流量最大的可行流。当fij=cij,则称流对边（vi,vj）是饱和的。本讲稿第四十五页，共五十五页最大流最小割最大流最小割本讲稿第四十六页，共五十五页最大流最小割最大流最小割在容量网络中割集是由vs到vt的必经之路，无论拿掉哪个割集，vs到vt便不再相通，所以任何一个可行流的流量不会超过任一割集的容量；定理：任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。本讲稿第四十七页，共五十五页最大流算法最大流算法增广链（路）容量网络G，为从vs到vt的一条链，给定向为从vs到vt，与同向的边称为
17、前向边，记为 与反向称为后向边，记为 f 为可行流，如果满足：则称记为为从vs到vt的一条增广链。本讲稿第四十八页，共五十五页最大流算法最大流算法标号算法标号算法思路：找出一条从发点输送正流到收点的链增广链，利用这条路把尽可能多的流从发点送到收点，重复这个过程，直到再也找不出增广链为止，这时网络上的流就是最大流。增广链：从发点到收点的链，前向弧的流量小于容量，后向弧的流量大于零。本讲稿第四十九页，共五十五页第一第一 标号过程标号过程可扩充量标号正向(Vi,Vj)反向(Vj,Vi)本讲稿第五十页，共五十五页第二第二 调整过程调整过程本讲稿第五十一页，共五十五页最大流问题最大流问题1 1VsV2V13,35,1V4V3Vt4,32,25,32,13,01,11,1c,f本讲稿第五十二页，共五十五页最大流问题最大流问题2 2VsV2V13,35,2V4V3Vt4,32,25,32,23,01,01,0本讲稿第五十三页，共五十五页习题习题4.24.2用标号法求图示的最短路本讲稿第五十四页，共五十五页习题习题4.34.3Va,Vb两城市公路网。弧上的数字为每段的距离（里数），求Va,Vb间的最短路。本讲稿第五十五页，共五十五页