《图与网络课件》由会员分享，可在线阅读，更多相关《图与网络课件（55页珍藏版）》请在金锄头文库上搜索。
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中移去这些边，则
5、G不连通，并且不存在这些边的真子集使图不连通图与网络最短路问题最短路问题设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年获得过素有计算机科学界的诺贝尔奖之称的图灵奖 1989年ACM SIGCSE计
6、算机科学教育教学杰出贡献奖 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类标号，则停止，否则转上一步。D D氏标号法步骤氏标号法步骤图与网络最短路问题
7、最短路问题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=4T(v3)=minT(v3), P(v1)+13=min,0+2=2 T(v4)=minT(v
8、4), 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), P(v3)+ 36=min,2+7=9v1(0)v2v7v5v411344452572v3(2)v6457图与网络最
9、短路算法最短路算法 (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)=minT(v5), P(v4)+ 45, P(v2)+ 25 =min,4+3,4+4=7 T(v6)=minT(v6), P(v4)+ 46=min9,4+4=8v
10、1(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标号的点，考察弧(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=1
11、47图与网络最短路算法最短路算法 (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)v2v7v5v411344452572(4)(4)(7)13(8)v3(2)v67图与网络最短路算法最短路算法 (11) 只有一个T标号T(v7)，令P(v7)=13 ，停止。v1(0)v2v7v5v411344452572(4)(
12、4)(7)(13)(8)v3(2)v67 计算结果见上图，v1到v7的最短路为：同时得到v1到其余各点的最短路。图与网络应用举例应用举例例：例：( (设备更新问题设备更新问题) ) 某企业在四年内都要使用某某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续种设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置使用旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：
13、时间（年）的设备的维修费用估计为： 年份1 12 23 34 4 年初购价1010111112121313 维修费用2 24 47 71414图与网络应用举例应用举例问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。图与网络最短路求法（最短路求法（2 2）构造长度矩阵L计算 其中图与网络最短路求法（最短路求法（2 2）长度矩阵图与网络最短路求法（最短路求法（2 2）表示vi到vj两步中距离最短的一条表示vi到vj两步不能到达图与网络最短路求法（最短路求法（2 2）图与网络最短路求法（最短路求法（2 2）
14、图与网络最短路求法（最短路求法（2 2）图与网络最短路求法（最短路求法（2 2）求任意两点最短距离均为mxn矩阵图与网络最短路求法（最短路求法（2 2）矩阵中元素为两点间最顿距离图与网络最大流引入最大流引入输油管道网，如何安排各管道的输油量，才能使从vs到vt总油量最大？图与网络最大流问题最大流问题管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量；如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。图与网络基本概念基本概念容量：G=(V,E)，每条边上有非负数cij称为边的容量；发点（源），收点（汇），中间点；对G中的边（vi,vj）有流量fi
15、j,称集合f=fij为网络G上的流；图与网络基本概念基本概念可行流容量限制：对G中的每条边（vi,vj）,有平衡条件：对中间点vi,有 对收点、发点有所谓最大流问题，就是在容量网络中，寻找流量最大的可行流。当fij=cij,则称流对边（vi,vj）是饱和的。图与网络最大流最小割最大流最小割图与网络最大流最小割最大流最小割在容量网络中割集是由vs到vt的必经之路，无论拿掉哪个割集，vs到vt便不再相通，所以任何一个可行流的流量不会超过任一割集的容量；定理：任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。图与网络最大流算法最大流算法增广链（路）容量网络G，为从vs到vt
16、的一条链，给定向为从vs到vt，与同向的边称为前向边，记为 与反向称为后向边，记为 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间的最短路。图与网络
