图论与网络规划模型课件.ppt

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

1、第5章图论与网络规划模型图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中许多方面都能提供有力的数学模型来解决实际问题。比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。第5章图论与网络规划模型5.1图的基本概念5.2最短路问题与最大流问题5.3最优连线问题与旅行商问题5.1.1图的定义5.1图的基本概念图G是一个偶对（V,E），其中V(G)={v1,v2,…,vn}为图的顶点集（vertexset），E

2、(G)={e1,e2,…,en}为图的边集（edgeset）或弧集（常用A表示）,记ek=(vi,vj)(k=1,2,…,m)。若ek是无序对，则称G为无向图（undirectedgraph）；若ek=(vi,vj)是有序对，则称G为有向图（directedgraph），vi为的起点，vj为的终点，称去掉有向图的方向得到的图为基础图（underlyinggraph）。5.1.1图的定义一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号

3、V

4、表示，边数用

5、E

6、表示。端点重合为一点的边称为

7、环(loop)。连接两个相同顶点的边的条数称为边的重数，重数大于1的边称为重边(multi-edges)。在有向图中，两个顶点相同但方向相反的边称为对称边(symmetricedge)。一个图称为简单图(simplegraph)，如果它既没有环也没有重边。5.1.2完全图、二分图、子图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。n个顶点的完全图记为Kn；完全图的定向图称为竞赛图。若V(G)=X∪Y，X∩Y=空集，

8、X

9、

10、Y

11、≠0,X中无相邻顶点对，Y中亦然，则称G

12、为二分图(bipartitegraph)；特别地，若对任意的x∈X,y∈Y，都有xy∈E(G)，则称G为完全二分图，记成K

13、X

14、,

15、Y

16、。G的支撑子图是指满足V(H)=V(G)的子图。若H是G的子图，则G称为H的母图。图H叫做图G的子图，记作，如果5.1.3顶点的度设v∈V(G)，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记作d(v)。若d(v)是奇数，称v是奇度顶点(oddpoint)；若d(v)是偶数，称v是偶度顶点(evenpoint)。对有向图，以v为起点的有向边数称

17、为v的出度(out-degree)，记作d+(v)；以为终点的有向边数称为的入度(in-degree)，记作d－(v)；顶点的度d(v)=d+(v)+d－(v)。5.1.4迹、路、圈与连通无向图G的一条途径(walk)是指一个有限的非空序列W=v0e1v1e2…ekvk，其中ei∈E(G)，1≤i≤k，vj∈V(G)，0≤j≤k，ei与vi-1vi关联，称k为W的长(length)。若途经的边互不相同，则称W为迹(trail)；若途径的顶点互不相同，则称W为路(path)；如果v0=vk，并且没有其

18、他相同的顶点，则称W为圈(cycle)。若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d(u,v)。若图G的任二顶点均连通，则称G是连通图。5.1.5图与网络的数据结构为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表

19、示法、邻接表表示法和星形表示法。首先假设G=(V,A)是一个简单有向图，

20、V

21、=n,

22、A

23、=m，并假设V中的顶点用自然数1,2,…,n表示或编号，A中的弧用自然数1,2,…,m表示或编号。5.1.5图与网络的数据结构-邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵（adjacencymatrix）的形式存储在计算机中。图G=(V,A)的邻接矩阵是如下定义的：C是一个n×n的矩阵，即5.1.5图与网络的数据结构-邻接矩阵表示法对于下图所示的有向图，可以用邻接矩阵表示为对于网络中的权，也可以用类似邻接矩阵

24、的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。无向图的邻接矩阵为对称阵。邻接矩阵举例n支球队循环赛，每场比赛只计胜负，没有平局.根据比赛结果排出各队名次.方法1.寻找按箭头方向通过全部顶点的路径.123456312456146325方法2.计算得分：无法排名2,3队,4,5队无法排名!6支球队比赛结果……32，45排名132456合理吗?1队胜4场，2,3队各胜3场，4,5队各胜2场，6队胜1场.123(1)123(2)1234(1)1234(