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

第五章 图论与网络分析,图的基本概念 最小支撑树问题 最短路径问题,学习目标,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,图的基本概念,哈密尔顿回路问题：环球旅行遊戏,欧拉回路：每边经过一次且仅一次的回路 哈密尔顿回路：每个点经过一次且仅一次的回路,问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?,图的基本概念,定义1：由点和边组成，记作G=(V，E)，其中 V=v1，v2，vn为结点的集合， E=e1，e2，em为边的集合。,点表示研究对象,边表示表示研究对象之间的特定关系,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,环，多重边，简单图 一条边的两个端点相同，称此边为环，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为二部图（偶图），有时记作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的支撑子图。,G2为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, 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处居民点都有道路相连，问至少要铺几条路？,【解】,该问题实为求图的支撑树问题，共需铺4条路。,图的支撑树的应用举例,最小支撑树问题,问题：求网络的支撑树，使其权和最小。,3、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数） 。,【例】 求上例中的最小支撑树,【解】,4,最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。,最小支撑树问题,3、最小支撑树问题,5,5.5,v1,v2,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，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,最小支撑树问题,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,此即为最经济的煤气管道路线，所需的总费用为25万元,最小支撑树问题,案例分析：默登公司的联网问题,默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。 问：需要铺设哪些光缆使得总成本最低？,最小支撑树问题,案例分析：默登公司的联网问题,最小支撑树问题,问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数lij（lij=表示vi、vj 间无边，vs、vt为图中任意两点，求一条道路 ，使从vs到vt的所有路中总权数最小。,最短路问题,解法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, v2,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的最短路,最短路问题,课堂练习,求无向图中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,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)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。,最短路问题,解法2：Floyd（弗洛伊德）算法,最短路问题,步骤： （1）输入权重矩阵