《图与网络》PPT课件

《《图与网络》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、络的基本概念V1V2V3de2e3e6e4e5V4V5e1V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5}G=(V,E)端点；关联边无向边；有向边（弧）环（自回路）多重边简单图；多重图悬挂点网络连通图点边序列；点边交替序列；在点边交替系列中，顺序排列的任意两条边均为相邻边，则称该点边交替序列为链；点边列中没有重复的点和重复边者称为初等链圈（回路）V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10链、路(1)链、路(2)v1a1v2a2v3a7v4v5a4a3a8a9路

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

4、cdefghkv1v2v6v3v4v5在一个连通图中割集是一些边的集合，从G中移去这些边，则G不连通，并且不存在这些边的真子集使图不连通最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权lij(lij=∞表示vi,vj之间无边)，vs,vt为图中任意两点，求一条路μ，使它是从vs到vt的所有路中总权数最小的路。最短路问题123434563234221EdsgerWybeDijkstra中文名：艾兹格·迪科斯彻家乡：荷兰出生年月：1930年5月11日去世年月：2002年8月6日成就：1972年获得

5、过素有计算机科学界的诺贝尔奖之称的图灵奖1989年ACMSIGCSE计算机科学教育教学杰出贡献奖2002年ACMPODC最具影响力论文奖D氏标号法思路：从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。条件：网络中所有的弧权为非负。开始给发点标上P(Vs)=0,其余节点标上临时标号T(Vj)=∞，j≠1;设节点Vi是刚得到的P类标号，把与节点Vi有弧直接相连而又属于T类标号的各节点Vj的标号改为：T(Vj)=min{T(Vj),P(Vj)+dij}在T类标号中选标号最小的节点Vj0，并把它的临时

6、标号T(Vj0)改为P(Vj0)，若终点获得P类标号，则停止，否则转上一步。D氏标号法步骤最短路问题•••••••v1v2v7v5v4171344452572v3v6最短路求解图中()内的数表示P标号，[]内的数表示T标号。•••••••v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7(1)首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+∞；最短路算法(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)属于D，且v2、v3、v4为T标

7、号，所以修改这三个点的标号：T(v2)=min{T(v2),P(v1)+ω12}=min{∞,0+4}=4T(v3)=min{T(v3),P(v1)+ω13}=min{∞,0+2}=2T(v4)=min{T(v4),P(v1)+ω14}=min{∞,0+5}=5•••••••v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]7最短路算法(3)比较所有T标号，T(v3)最小，故令P(v3)=2•••••••v1(0)v2v7v5v411344452572v3(2)v6

8、[4][5][∞][∞][∞]7最短路算法(4)v3为刚得到P标号的点，考察弧(v3,v4)，(v3,v6)的端点v4,v6T(v4)=min{T(v4),P(v3)+ω34}=min{5,2+2}=4T(v6)=min{T(v6),P(v3)+ω36}=min{∞,2+7}=9•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7最短路算法(5)比较所有T标