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

第五章图论与网络分析图的基本概念最小支撑树问题最短路径问题学习目标ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？图的基本概念定义1：由点和边组成，记作G=(V，E)，其中

V={v1，v2，……，vn}为结点的集合，E={e1，e2，……，em}为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图图的基本概念注意：上面定义的图Ｇ区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。V、E为有限集合，则为有限图，反之无限图。v3e7e4e8e5e6e1e2e3v1v2v4v5【例】图5－1，边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的关联边。图5－1e6可记作：图的基本概念端点，相邻，关联边图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1环，多重边，简单图

一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e52、图的分类定义2：无环、无多重边的图称作简单图。

含有多重边的图为多重图。图的基本概念定义3：每一对顶点间都有边相连的无向简单图，称为

完全图。有n个顶点的无向完全图记为Kn。2、图的分类定义4：图G=(V,E)的点集V可分为两个非空子集X、Y，

即X∪Y=V，X∩Y=∅，使得E中每条边的两个

端点必有一个端点属于X，另一个端点属于Y，

则称G为二部图（偶图），有时记作G=(X,Y,E)。图的基本概念3、顶点的次定义5：以点v为端点的边数叫点v的次

（degree），记作deg(v)或d(v)。v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1图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的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2图的基本概念v1v2v3v4v56、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：图的基本概念没有重复点和重复边的链为初等链。初等圈7、连通图定义10：任意两点之间至少存在一条链的图称为连通图，

否则称为不连通图。G1G2G1为不连通图，G2为连通图例：图的基本概念图的基本概念8、图的矩阵表示定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵A=(aij)n×n，其中：

则称矩阵A为网络G的权矩阵。（vi，vj）∈E其他树支撑树最小支撑树【例】今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数–1。1、树连通且无圈的无向图(A)(B)(C)树的性质：判断下面图形哪个是树：最小支撑树问题

若一个图G=（V,E）的支撑子图T=（V,E´）构成树，则称T为G的支撑树，又称生成树、部分树。2、图的支撑树(G)(G1)(G2)(G3)(G4)最小支撑树问题问题：求网络的支撑树，使其权和最小。3、最小支撑树问题算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。【例】

求上例中的最小支撑树【解】3v12v4v545v23.5v3最小支撑树问题55.5v1v2v3v4v57.53.5423算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.5423最小支撑树问题3、最小支撑树问题算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树问题55.5v1v2v3v4v53.5423算法2（破圈法）：在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树问题5v1v2v3v4v53.523

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

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

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

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

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元最小支撑树问题案例分析：默登公司的联网问题

默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？ABCEGFD252745713144图1光缆铺设费用图最小支撑树问题ABCEGFD225131图1光缆铺设最小费用图案例分析：默登公司的联网问题最小支撑树问题问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数lij（lij=∞表示vi、vj间无边，vs、vt为图中任意两点，求一条道路µ，使从vs到vt的所有路中总权数最小。v2v1v3v4v5v6v7v8v9163222266133101044【例】求网络中v1到v9的最短路最短路问题解法1：Dijkstra（狄克斯拉）标号法基本思想：从起点vs开始，逐步给每个结点vj标号[dj，vi]，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。最短路问题10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](1)

给起点v1标号[0,v1](3)

考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)

重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)

把顶点集V分成VA：已标号点集VB：未标号点集[0,v1][1,v1][3,v1](1)

给起点v1标号[0,v1](3)

考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)

重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)

把顶点集V分成VA：已标号点集VB：未标号点集10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此时终点v9已标号[12,v5]，则12即为v1→vn的最短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路为：v1→v3→v2→v5→v9，最短距离为1210v2v1v3v4v5v6v7v8v91632222661331044[课堂练习][0,v1][4,v1][3,v1][5,v2][6,v2][9,v7][7,v4/v6][8.5,v6][6,v2]v2v1v5v4v3v6v8v7v943232.533523421最短路问题求网络中v1到v9的最短路v1v2v3v4v5v6v7225355715713最短路问题[课堂练习]求无向图中v1到v7的最短路答案：路径一v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]最短路问题v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]最短路问题答案：路径二【例】最短路模型的应用——设备更新问题v2v1v3v4v5v6第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]16分析：顶点：V={v1，…，v6}，vi表示第i年初；边：E={(vi，vj)}表示第i年初购买，用至第j年初；i=1,…,5;j=2,…,6权cij：i年初~j年初的费用，即cij=i年初购买费+（j-i）年里的维修费3022415916223041172331172318最短路问题【例】某连锁企业在某地区有6个销售点，已知该地区的交通网络如下图所示，其中点代表销售点，边代表公路，lij为销售点间公路的距离，问仓库健在哪个销售点，可使仓库离最远销售点到仓库的路程最近？v2v1v4v3v5v66030202520151518v1v2v3v4v5v6D(vi)v10203363153063v22002050254050v33320