图论模型(最优连线问题、最短路问题)ppt课件.ppt

《图论模型(最优连线问题、最短路问题)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ch8图论模型图论是离散数学的重要分支，在物理学、化学、系统工程、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域又具有极其广泛的应用。图论的历史可以追朔到1736年，这一年29岁的瑞士大数学家Euler发表了图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。现实生活中的公路交通网、铁路交通网、灌溉网、自来水（石油、天然气）管道网、电话线网计算机通讯网、输电线网等，都可以用上述图的方式来描述和分析解决问题。著名数学家欧拉七桥问题图的基本概念1定义：由顶点和边组成的图形称为图。uev2边e与顶点u、v相关联。顶点u与v

2、相邻。边e1与e2相邻。u=v时，边e称为环。3度定义：与顶点v关联的边的数目称为顶点v的度数，记为d(v)。（注：环算2度。）对于有向图的顶点的度数，还可分为出度和入度。定理：4图的矩阵表示①关联矩阵无向图G，关联矩阵M=（mij）有向图G，关联矩阵M=（mij）例1v1v2v3v4e1e4e2e3e5②邻接矩阵无向图G，邻接矩阵A=（aij）有向图G，邻接矩阵A=（aij）有向赋权图G，邻接矩阵A=（aij）例2v1v2v3v4e1e4e2e3e5v1v2v3v4v1v2v3v4例3v1v2v3v428357v1v2v3v4

3、v1v2v3v48.1最优连线问题（最小生成树）例1现需从自来水厂接自来水管道到各个城镇，自来水厂到各城镇之间铺设自来水管道价格如下，问如何铺设最经济。水厂853191076ABCDE分析：①显然铺设的自来水管道要连通各个顶点；②铺设的管道中如果有回路，则去掉一条边，仍可行。故所铺设的管道是连通各个顶点且没有回路的图形，称为图G的生成树。我们的目标是寻找一颗图G的生成树，其各条边的权之和最小，称为最小生成树。1956年，Kruskal给出了一种求最小生成树的算法，称为避圈法。算法如下：（1）选择边，使得最小；（2）若已经选定边，

4、则从剩余边集中选取，使①新选边与之前选择的边组成图为无圈图，②新选边是满足①的尽可能小的权。（3）当（2）不能继续执行时停止。（其思想是：在剩余边集中找边权最小的边添加到生成树中，同时又不能产生回路即以局部的最优谋求全局的最优。）上述的描述实际上是最小生成树的逐步生长过程，上例的最小生成树如下：水厂853191076ABCDEPrim算法：1)在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U={v0}，集合T(E)为空。2)从v0出发寻找与U中顶点相邻（另一顶点在V中）

5、权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1}，同时将该边加入集合T(E)中。3)重复(2)，直到U=V为止。这时T(E)中有n-1条边，T=(U,T(E))就是一棵最小生成树。（其思想是：在剩余点集中找连接到U中顶点的最小权重的边，添加到生成树中。（显然不会产生回路）。仍然是以局部的最优谋求全局的最优。）上例中，采用Prim算法最小生成树的生长过程：水厂853191076ABCDE72911492126314678例：如何设计海底管道网。（Prim算法）有兴趣可以用Kruskal算法计算一下，看是否有区别

6、。8.2最短通路问题1Dijkstra算法在各种网络的铺设、网络的输送、线路的安排等问题中，经常涉及确定一条最短路。1959年，荷兰数学家E.W.Dijkstra给出了该问题的一个解法。32101695115710852u1u2u3u4u5u6u7u8解：算法原理为蚂蚁算法（探索算法），每次新连接一个点。所有新到一个点最短路程中最短的那个店，作为新增点。第一步：找从u1出发到达的距离最近的点u4，min{2,8,1}，将这个距离写进u4的圈中。将从u1到u4的边描成红色，u4成为永久标记的点；32101695115710852u

7、1u2u3u4u5u6u7u801第二步：在其余点中找从u1直接到达或从u1经u4到达的距离最近的点u2，min{2,8,11,11}。将这个距离写进u2的圈中，将u1到u2的边描红，u2成为永久的标志的点；32101695115710852u1u2u3u4u5u6u7u8012第三步：在其余点中找从u1直接到达或从u1经u4到达或从u1经u2到达的的距离最近的点u5，min{8,11,11,3,9}。32101695115710852u1u2u3u4u5u6u7u80123第四步：min{8,11,11,9,8,6,12}，u

8、6。32101695115710852u1u2u3u4u5u6u7u801236第五步：min{8,11,11,9,8,12,7,11,11}，u3。32101695115710852u1u2u3u4u5u6u7u8012367第六步：min{11,12,11,