第8章 图与网络分析3.ppt

第八章 图与网络分析; 关于图的第一篇论文是瑞士数学家欧拉(E. Euler)在1736年发表的解决“哥尼斯堡” 七桥难题的论文； 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图形的一笔画问题。;哥尼斯堡七桥问题;哥尼斯堡七桥问题可简化为以下图形,其中的四个顶点都是奇顶点;;图与网络分析; 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。;例1下图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。;例2有六支球队进行足球比赛，我们分别用点v1 ，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2 队，v2 队战胜v3 队，v3 队战胜v5队，如此等等。这个胜负情况，可以用有向图反映出来; 从以上的例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。;图与网络的基本概念;图与网络的基本概念;图与网络的基本概念;;图与网络的基本概念;图与网络的基本概念;图与网络的基本概念;图与网络的基本概念;链：对于无向图G =（V,E）, 称顶点和边交替的序列 ;;连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。 ; 图的图形表示法在较为简单的情况下由于比较直观，所以有一定的优越性，但对于比较复杂的图这种表示方法就不太方便了。故目前一般多用矩阵方法表示图。由于这种方法表示简单，使用方便，目前应用较为普遍。更重要的是，它把图的问题变成为数学计算问题，因而对图的研究可借助于计算机来实现。图的矩阵表示法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里仅介绍其中的两种。;定义：对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。;例 如图所示，其权矩阵为： ;定义 设图G=（V，E）中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。;邻接矩阵为： 因为G是无向图，所以邻接矩阵是对称的。;图与网络分析; 树;一、树的概念和性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 例已知有 5个城市，要在它们之间架设电话线网，要求任何两个城市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。;图8.8;树的基本概念与性质;图的生成树;图的生成树;1) 破圈法 破圈法思路：任取一圈，从圈中去掉任一条边，再对余下的圈重复相同的步骤，直到图中所有的圈破掉为止。 2）避圈法 避圈法思路：将不连通的无圈图通过边的增加，逐步变成连通无圈图。 ;最小生成树的定义—— 一颗生成树上所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树为最小生成树。;最小生成树的求法－避圈法;v1;最小生成树的求法－避圈法;最小生成树的求法－避圈法;最小生成树的求法－避圈法; 例2 某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。;v3;最小生成树的求法－破圈法;最小生成树的求法－破圈法;最小生成树的求法－破圈法; 例2 某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短,用破圈法求解; 例 3 用破圈法求出下图中的最小生成树;例4 用避圈法求出下图中的最小生成树;图与网络分析;最短路径问题;求解最短路的方法很多，该问题完全可以看成一个网络问题，可以利用后面的最小费用流算法可以求解，也可以用前面介绍的动态规划方法求解。但计算效率最高的还是图论的方法。; (Dijkstra)算法 它是在1959年提出来的。目前公认，在所有的权wij ≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻