图论中几个典型问题的求解.ppt

《图论中几个典型问题的求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论中几个典型问题的求解§1图的基本概念图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。一、图的定义图论是以图为研究对象的数学分支，在图论中，图由一些点和点之间的连线所组成．称图中的点为顶点（节点），称连接顶点的没有方向的线段为边，称有方向的线段为弧．用V={v1,v2,…}表示全体顶点的集合，用E={e1,e2,…}表示全体边的集合，如果对于E中的任一条边ek，在V中都有一对顶点(vi,vj)和它对应，则称由V和E组成的集体为一个图，记为G={V,E}，简写为G．二、基本概念点与边相连接称为关联，与边e关

2、联的顶点称为该边的端点，与同一条边关联的两个顶点称为相邻顶点，与同一个顶点关联的边称为相邻边．具有相同顶点的边称为平行边，两个端点重合的边称为环．所有线段都没有方向的图称为无向图，所有线段都有方向的图称为有向图，既有边也有弧的图称为混合图．在无向图中，没有环和平行边的图称为简单图，任意两个顶点之间都有一条边相连的简单图称为完全图．任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图．在无向图中与顶点v关联的边的数目（环算两次）称为该顶点的度（或次数），记为d(v)。度为奇数的顶点叫做奇点，度为偶数的顶点叫做偶点。在有向图中，从顶点v引出的边的数目称为该顶点的出度，记为d+(v

3、)，从顶点v引入的边的数目称为该顶点的入度，记为d-(v)，而d(v)＝d+(v)+d-(v)称为v的次数。在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）．包含奇数个顶点（或边）的圈称为奇圈，包含偶数个顶点（或边）的圈称为偶圈。如果顶点u和v之间存在一条路，则称u和v是连通的，任意两个顶点都连通的图称为连通图．无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树．如果图G

4、的每条边e都对应一个实数C(e)，称C(e)为该边e的权，称图G为赋权图．通常称赋权的有向图为网络．图中边e6和e7是平行边，e9是环，顶点v4是悬挂点，边e4是悬挂边．§2最短路问题最短路问题是图论应用的基础，很多实际问题，如线路的布设、运输规划、运输网络最小费用流等问题，都可以通过建立最短路模型来求解。有些有深度的图与网络优化问题，如旅行售货商、中国邮递员等问题，需要在首先求出任意两点之间最短路的基础上解决。一、最短路的概念给定一个连通的赋权图G={V,E}，设R是连接节点vi和vj的一条路，该路的权定义为路中所有各边权之和，如果路R在所有连接节点vi和vj的路中权最小，

5、则称它为vi和vj间的最短路。二、任意两点之间的最短路(Floyd算法)Floyd算法利用距离矩阵进行迭代运算，可以一次性地求出任意两点之间的最短路，该方法的思路有创意，计算量小，编程较简单，又称矩阵求解法。1．算法原理设A=[aij]m×n是图的权矩阵（也称带权邻接矩阵），其中aij是图上连接顶点i和j的边的权，如果两顶点之间没有直接相连的边（即两顶点不相邻），则aij=∞。令矩阵D(0)=A，作为迭代的初始矩阵，从它出发按照一定规则求D(1)，又由D(1)按照类似的规则求D(2)，依此类推进行迭代直至求出D(n)，设矩阵D(m)的元素为dij(m)，迭代规则为：上式表示d

6、ij(1)在dij(0)以及从顶点vi经过顶点v1到vj的权之和di1(0)+d1j(0)两者之中选择最短长度。依此规则迭代。上式表示dij(2)在dij(1)以及从顶点vi经过顶点v2到vj的权之和di2(1)+d2j(1)两者之中选择最短长度。依此类推，迭代公式为：上式表示dij(m)在dij(m-1)以及从顶点vi经过顶点vm到vj的权之和dim(m-1)+dmj(m-1)两者之中选择最短长度。当m=n时结束迭代。2．程序设计先编写Flody算法的子程序（函数）如下：Function[D,R]=floyd(a)n=size(a,1);D=a;%D是初始矩阵fori=1:

7、nforj=1:nR(i,j)=j;endendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)