《运筹学教程》胡云权第五版第五章图与网络分析.ppt

《《运筹学教程》胡云权第五版第五章图与网络分析.ppt》由会员分享，可在线阅读，更多相关《《运筹学教程》胡云权第五版第五章图与网络分析.ppt（56页珍藏版）》请在三一办公上搜索。

1、第五章 图论与网络分析,图的基本概念 最小支撑树问题 最短路径问题,学习目标,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,图的基本概念,哈密尔顿回路问题：环球旅行遊戏,欧拉回路：每边经过一次且仅一次的回路哈密尔顿回路：每个点经过一次且仅一次的回路,问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?,图的基本概念,定义1：由点和边组成，记作G=(V，E)，其中 V=v1，v2，vn为结点的集合，E=e1，e2，em为边的集合。,点表示研究对象,边表示表示研究

2、对象之间的特定关系,1.图,图的基本概念,注意：上面定义的图区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。,V、E为有限集合，则为有限图，反之无限图。,【例】图51，,边e=vi，vj，称vi和vj是边e的端点，vi和vj 两点相邻；边ex和ey有公共端点vi，称边ex和ey相邻，边ex和ey为点vi 的关联边；,v2和v4是边e6的端点，点v2、v4相邻。e6与e7共用顶点v4，e6与e7相邻，e6和e7为点v4的关联边。,图51,e6可记作：,图的基本概念,端点，相邻，关联边,图的基本概念,图51,环，多重边，简单图

3、 一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e5,2、图的分类,定义2：无环、无多重边的图称作简单图。含有多重边的图为多重图。,图,无向图，记作G=(V，E),有向图，记作D=(V，A),例1：哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,图的基本概念,图的基本概念,定义3：每一对顶点间都有边相连的无向简单图，称为 完全图。有n个顶点的无向完全图记为Kn。,2、图的分类,定义4：图G=(V,E)的点集V可分为两个非空子集X、Y，即XY=V，XY=，使得E中每条边的两个 端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），有

4、时记作G=(X,Y,E)。,图的基本概念,3、顶点的次,定义5：以点v为端点的边数叫点v的次（degree），记作deg(v)或d(v)。,图51,图5-1中，d(v1)，d(v3)=5，d(v5)=1。,次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。次为1的点称作悬挂点，连接悬挂点的边为悬挂边。图的次：各点的次之和。有向图中顶点的次？,定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点为偶数个。,4、子图、支撑子图,图G=(V,E)和G=(V,E)，若V V，E E，则称G 为G的子图。特别地，若V=V 且E E，则称G 为G的支撑子图。,G

5、2为G1的支撑子图,图的基本概念,5、赋权图（网络）,图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。,图的基本概念,6、链与路、圈与回路,链,点边交错的序列,路,点弧交错的序列,回路,起点=终点的路,无向图：,有向图：,图的基本概念,没有重复点和重复边的链为初等链。初等圈,7、连通图,G1为不连通图，G2为连通图,例：,图的基本概念,图的基本概念,8、图的矩阵表示,定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵 A=(aij)nn，其中：则称矩阵A为网络G的权矩阵。,（vi，vj）E,其他,图的基本概念,8、图的矩阵表示,定义12：图G=(V

6、,E)，|V|=n，构造一个矩阵 A=(aij)nn，其中：则称矩阵A为图G的邻接矩阵。,（vi，vj）E,其他,树,支撑树,最小支撑树,最小支撑树问题,1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数 1。,1、树,连通且无圈的无向图,树的性质：,判断下面图形哪个是树：,最小支撑树问题,若一个图 G=（V,E）的支撑子图 T=（V,E）构成树，则称 T 为G的支撑树，又称生成树、部分树。,2、图的支撑树,最小支撑树问题,【例】某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至

7、少要铺几条路？,【解】,该问题实为求图的支撑树问题，共需铺4条路。,图的支撑树的应用举例,最小支撑树问题,问题：求网络的支撑树，使其权和最小。,3、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。,【例】求上例中的最小支撑树,【解】,最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,5,5.5,v1,v

8、2,v3,v4,v5,3.5,4,2,3,5,v1,v2,v3,v4,v5,3.5,4,2,3,最小支撑树问题,3、最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,5,v1,v2,v3,v4,v5,3.5,2,3,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例

9、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支

10、撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费

11、用。,此即为最经济的煤气管道路线，所需的总费用为25万元,最小支撑树问题,案例分析：默登公司的联网问题,默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？,最小支撑树问题,案例分析：默登公司的联网问题,最小支撑树问题,问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数lij（lij=表示vi、vj 间无边，vs、vt为图中任意两点，求一条道路，使从vs到vt的所有路中总权数最小。,最短路问题,

12、解法1：Dijkstra（狄克斯拉）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。,最短路问题,0,v1,1,v1,(1)给起点v1标号0,v1,(3)考虑所有这样的边vi,vj，其中viVA，vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4)重复(2)、(3)，直至终点vn标上号dn,vi，则dn即为v1 vn的最短距离，反向追踪可求出最短路。,步骤：,0,v1,1,v1,3,v1,0,v1,1,v1,3,v1,5,v3,0,v1,1,v1,3,v1,5,v3,6,v

13、2,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,此时终点v9已标号12,v5，则12即为v1 vn的最短距离，反向追踪可求出最短路,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,v1到v9的最短路为：v1 v3 v2 v5 v9，最短距离为12,课堂练习,0,v1,4,v1,3,v1,5,v2,6,v2,9,v7,7,v4/v6,8.5,v6,6,v2,最短路问题,求网络中v1到v9的最

14、短路,最短路问题,课堂练习,求无向图中v1到v7的最短路,答案：路径一,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/v4,7,v3,8,v5,13,v6,最短路问题,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/v4,7,v3,8,v5,13,v6,最短路问题,答案：路径二,【例】最短路模型的应用设备更新问题,16,分析：,顶点：V=v1，v6，vi表示第i年初；,边：E=(vi，vj)表示第i年初购买，用至第j年初；i=1,

15、5;j=2,6,权cij：i年初 j年初的费用，即cij=i年初购买费+（j-i）年里的维修费,30,22,41,59,16,22,30,41,17,23,31,17,23,18,最短路问题,【例】某连锁企业在某地区有6个销售点，已知该地区的交通网络如下图所示，其中点代表销售点，边代表公路，lij为销售点间公路的距离，问仓库健在哪个销售点，可使仓库离最远销售点到仓库的路程最近？,【解】,最短路问题,解法2：Floyd（弗洛伊德）算法,基本思想：从图的权矩阵D=(dij)nn开始，递归地进行n次更新，即由矩阵D(0)=D，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最

16、后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。,最短路问题,解法2：Floyd（弗洛伊德）算法,最短路问题,步骤：（1）输入权重矩阵D(0)=D（2）计算D(k)=(dij(k)nn(k=1,2,n)其中，dij(k)=mindij(k-1)，dik(k-1)+dkj(k-1)（3）D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。,【例】求图G中任意两点的最短路,最短路问题,【解】图G的权矩阵,表示从vi点到vj点或直接有边，或经v1为中间点时的最短路长,最短路问题,表示从vi点到vj点或直接有边，或最多经v1 v2为中间点时的最短路长,作业,P2568.18.6,