1、第五章 图论与网络分析学习目标学习目标ABCDACBD图论起源图论起源哥尼斯堡七桥问题哥尼斯堡七桥问题结论结论：每个结点关联的边数均为偶数。：每个结点关联的边数均为偶数。问题问题：一个散步者能否从任一块陆地出发，走过七：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？图的基本概念图的基本概念哈密尔顿回路问题：环球旅行遊戏哈密尔顿回路问题：环球旅行遊戏欧拉回路：欧拉回路：每边经过一次且仅一次的回路每边经过一次且仅一次的回路哈密尔顿回路：哈密尔顿回路：每个点经过一次且仅一次的回路每个点经过一次且仅一次的回路问题问题：游戏者从
2、任一城市出发，寻找一条可经过每：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路个城市一次且仅一次，在回到原出发点的路?图的基本概念图的基本概念1234567891011121314151617181920定义定义1 1：由点和边组成，记作由点和边组成，记作G=(VG=(V，E)E)，其中，其中 V=vV=v1 1，v v2 2，v vn n 为结点的集合，为结点的集合，E=eE=e1 1，e e2 2，e em m 为边的集合为边的集合。点点表示研究对象表示研究对象边边表示表示研究对象之间的特定关系表示表示研究对象之间的特定关系 1.图图图的基本概念图的基本概念注
3、意：注意：上面定义的图区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。V、E为有限集合，则为为有限集合，则为有限图有限图，反之无限图。，反之无限图。v3e7e4e8e5e6e1e2e3v1v2v4v5【例】图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的关联边。图51e6可记作：12345,Vv v v v v图的基
4、本概念图的基本概念端点，相邻，关联边端点，相邻，关联边1238,Ee e ee624,ev v(,)GV E图的基本概念图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5图51环，多重边，简单图环，多重边，简单图 一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e5 2、图的分类、图的分类定义定义2：无环、无多重边的图称作简单图。含有多重边的图为多重图。图图无向图，记作无向图，记作G=(V，E)有向图，记作有向图，记作D=(V，A)例例1：哥尼斯堡桥问题的图为一个无向图。：哥尼斯堡桥问题的图为一个无向图。有向图的边有向图的边称为称为弧弧。例例2：五个
5、球队的比赛情况，：五个球队的比赛情况，v1v2表示表示v1胜胜v2。v1v2v3v4v5 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)或
6、d(v)。v3e7e4e8e5e6e1e2e3v1v2v4v5图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的支撑子图的支撑子图v1v2v3v4v5G
7、1v1v2v3v4v5G2图的基本概念图的基本概念 5、赋权图（网络）、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称图的每条边都有一个表示一定实际含义的权数，称为为赋权图赋权图。记作。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423图的基本概念图的基本概念v1v2v3v4v5 6、链与路、圈与回路、链与路、圈与回路链链点边交错的序列点边交错的序列圈圈起点起点=终点的链终点的链路路点弧交错的序列点弧交错的序列回路回路起点起点=终点的路终点的路v1v2v3v4v5无向图：无向图：有向图：有向图：图的基本概念图的基本概念没有重复点和重复边的链为初等链。初等圈没有重
8、复点和重复边的链为初等链。初等圈 7、连通图、连通图定义定义10：任意两点之间至少存在一条链的图称为连通图，任意两点之间至少存在一条链的图称为连通图，否则称为不连通图。否则称为不连通图。G1G2G1为不连通图，为不连通图，G2为连通图为连通图例例：图的基本概念图的基本概念图的基本概念图的基本概念 8、图的矩阵表示、图的矩阵表示定义定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵 A=(aij)nn，其中：则称矩阵A为网络G的权矩阵。0ijijwa（vi，vj）E其他图的基本概念图的基本概念 8、图的矩阵表示、图的矩阵表示定义定义12：图图G=(V,E)，|V|=n，构造一个矩
9、阵 A=(aij)nn，其中：则称矩阵A为图G的邻接矩阵。10ija（vi，vj）E其他树树支撑树支撑树最小支撑树最小支撑树【例】今有煤气站【例】今有煤气站A，将给一居民区供应煤气，居民区，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题最小支撑树问题1、树中
10、任两点中有且仅有一条链；、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。少边数的一种图形。3、边数、边数=顶点数顶点数 1。1、树、树连通且无圈的无向图连通且无圈的无向图(A)(B)(C)树的性质：树的性质：判断下面图形哪个是树：判断下面图形哪个是树：最小支撑树问题最小支撑树问题 若一个图若一个图 G=（V,E）的支撑子）的支撑子图图 T=（V,E）构成树，则称构成树，则称 T 为为G的支撑树的支撑树，又称，又称生成树生成树、部分树部分树。2、图的支撑树、图的支撑树(G)(G1)(G2)(G3
11、)(G4)最小支撑树问题最小支撑树问题【例】【例】某地新建某地新建5处居民点，拟修处居民点，拟修道路连接道路连接5处，经勘测其道路可铺成处，经勘测其道路可铺成如图所示。为使如图所示。为使5处居民点都有道路处居民点都有道路相连，问至少要铺几条路？相连，问至少要铺几条路？【解】【解】该问题实为求图的支撑该问题实为求图的支撑树问题，共需铺树问题，共需铺4条路。条路。v1v2v3v4v5 图的支撑树的应用举例图的支撑树的应用举例v1v2v3v4v555.57.53.5423最小支撑树问题最小支撑树问题问题：问题：求网络的支撑树，使其权和最小。求网络的支撑树，使其权和最小。3、最小支撑树问题、最小支撑树
12、问题算法算法1（避圈法）：（避圈法）：把边按权从小到大依次把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，添入图中，若出现圈，则删去其中最大边，直至填满直至填满n-1条边为止（条边为止（n为结点数）为结点数）。【例】【例】求上例中的最小支撑树求上例中的最小支撑树【解】【解】3v12v4v545v23.5v3最小支撑树问题最小支撑树问题55.5v1v2v3v4v57.53.5423算法算法2（破圈法）：（破圈法）：在图中找圈，并删除其中权数最大在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。的边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.
13、5423最小支撑树问题最小支撑树问题 3、最小支撑树问题、最小支撑树问题算法算法2（破圈法）：（破圈法）：在图中找圈，并删除其中权数最大在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。的边。如此进行下去，直至图中不存在圈。最小支撑树问题最小支撑树问题 3、最小支撑树问题、最小支撑树问题55.5v1v2v3v4v53.54235v1v2v3v4v53.5423最小支撑树问题最小支撑树问题 3、最小支撑树问题、最小支撑树问题算法算法2（破圈法）：（破圈法）：在图中找圈，并删除其中权数最大在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。的边。如此进行下去，直至
14、图中不存在圈。算法算法2（破圈法）：（破圈法）：在图中找圈，并删除其中权数最大在图中找圈，并删除其中权数最大的边。如此进行下去，直至图中不存在圈。的边。如此进行下去，直至图中不存在圈。最小支撑树问题最小支撑树问题 3、最小支撑树问题、最小支撑树问题5v1v2v3v4v53.523 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的
15、总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题最小支撑树问题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531最小支撑树问题最小支撑树问
16、题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531最小支撑树问题最小支撑树问题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需
17、用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531最小支撑树问题最小支撑树问题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计
18、一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531最小支撑树问题最小支撑树问题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531最小支撑树问题
19、最小支撑树问题 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为25万元万元最小支撑树问题最小支撑树问题案例分析：案例分析：默登公司的联网问题默登公
20、司的联网问题 默登（默登（ModernModern）公司的管理层决定铺设最先进的光纤）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图网络，为它的主要中心之间提供高速通信。图1 1中的节点显中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。每条虚线旁边的数字表示成本（单位：百万美元）。问：问：需要铺设哪些光缆使得总成本最低？需要铺设哪些光缆使得总成本最低？A AB BC CE EG GF FD D2 25 52 27 74 45 57 71 13 31 14
21、 44 4图图1 1 光缆铺设费用图光缆铺设费用图最小支撑树问题最小支撑树问题ABCEGFD225131图图 1 光缆铺设最小费用图光缆铺设最小费用图案例分析：案例分析：默登公司的联网问题默登公司的联网问题最小支撑树问题最小支撑树问题问题描述：问题描述：设G=(V,E)为连通图，图中各边(vi，vj)有权数lij（lij=表示vi、vj 间无边，vs、vt为图中任意两点，求一条道路，使从vs到vt的所有路中总权数最小。v2v1v3v4v5v6v7v8v9163222266133101044【例】【例】求网络中求网络中v1到到v9的最短路的最短路最短路问题最短路问题解法解法1：Dijkstra（
22、狄克斯拉）标号法（狄克斯拉）标号法基本思想：基本思想：从起点从起点vs开始，逐步给每个结开始，逐步给每个结点点vj标号标号dj，vi，其中，其中dj为起点为起点vs到到vj的的最短距离，最短距离，vi为该最短路线上的前一节点。为该最短路线上的前一节点。最短路问题最短路问题10v2v1v3v4v5v6v7v8v916322226613310440,v11,v1(1)给起点给起点v1标号标号0,v1(3)考虑所有这样的边考虑所有这样的边vi,vj，其中，其中viVA，vjVB，挑选，挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4)重复
23、重复(2)、(3)，直至终点，直至终点vn标上号标上号dn,vi，则，则dn即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2)把顶点集把顶点集V分成分成VA：已标号点集：已标号点集VB：未标号点集：未标号点集0,v11,v13,v1(1)给起点给起点v1标号标号0,v1(3)考虑所有这样的边考虑所有这样的边vi,vj，其中，其中viVA，vjVB，挑选，挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4)重复重复(2)、(3)，直至终点，直至终点vn标上号标上号dn,vi，则，则d
24、n即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2)把顶点集把顶点集V分成分成VA：已标号点集：已标号点集VB：未标号点集：未标号点集10v2v1v3v4v5v6v7v8v916322226613310440,v11,v13,v15,v310v2v1v3v4v5v6v7v8v916322226613310440,v11,v13,v15,v36,v210v2v1v3v4v5v6v7v8v916322226613310440,v11,v13,v15,v36,v29,v510v2v1v3v4v5v6v7v8v916322226613310440,
25、v11,v13,v15,v36,v29,v510,v510v2v1v3v4v5v6v7v8v916322226613310440,v11,v13,v15,v36,v29,v510,v512,v5此时终点此时终点v9已标号已标号12,v5，则，则12即为即为v1 vn的最的最短距离，反向追踪可求出最短路短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v916322226613310440,v11,v13,v15,v36,v29,v510,v512,v5v1到到v9的最短路为：的最短路为：v1 v3 v2 v5 v9，最短距离为最短距离为1210v2v1v3v4v5v6v7v8v9
26、1632222661331044课堂练习课堂练习0,v14,v13,v15,v26,v29,v77,v4/v68.5,v66,v2v2v1v5v4v3v6v8v7v943232.533523421最短路问题最短路问题求网络中求网络中v1到到v9的最短路的最短路v1v2v3v4v5v6v7225355715713最短路问题最短路问题课堂练习课堂练习求无向图中求无向图中v1到到v7的最短路的最短路答案：路径一答案：路径一v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/v47,v38,v513,v6最短路问题最短路问题v1v2v3v4v5v6v722535571
27、57130,v12,v13,v14,v2/v47,v38,v513,v6最短路问题最短路问题答案：路径二答案：路径二【例】最短路模型的应用【例】最短路模型的应用设备更新问题设备更新问题v2v1v3v4v5v6第第i年年价格价格ai111211312412513使用寿命使用寿命费用费用bj015126238341145180,v116,v122,v130,v141,v153,v3/v416分析分析：顶点顶点：V=v1，v6，vi表示第表示第i年初；年初；边边：E=(vi，vj)表示第表示第i年初购买，用至第年初购买，用至第j年初；年初；i=1,5;j=2,6权权cij：i年初年初 j年初的费用，
28、即年初的费用，即cij=i年初购买费年初购买费+（j-i）年里的维修费）年里的维修费3022415916223041172331172318最短路问题最短路问题【例】某连锁企业在某地区有6个销售点，已知该地区的交通网络如下图所示，其中点代表销售点，边代表公路，lij为销售点间公路的距离，问仓库健在哪个销售点，可使仓库离最远销售点到仓库的路程最近？v2v1v4v3v5v66030202520151518v1v2v3v4v5v6v102033631530v220020502540v333200301833v463503004863v515251848015v630403363150D(vi)635
29、033634863【解】【解】最短路问题最短路问题解法解法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）输入权重矩阵
30、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中任意两点的最短路最短路问题最短路问题v2v3v4v6v5v12025201560301815【解】图G的权矩阵(0)02015200206025200301860300152518015150DD(1)(0)(0)(0)11min,ijijijdddd表示从vi点到vj点或直接有边，或经v1为中间点时的最短路长(1)(0)(0)(0)(0)111111111
31、1min,0ddddd(1)(0)(0)(0)(0)1212111212min,20ddddd(1)(0)(0)(0)(0)1313111313min,ddddd(1)(0)(0)(0)(0)2121211121min,20ddddd(1)(0)DD最短路问题最短路问题(2)(1)(1)(1)22min,ijijijdddd表示从vi点到vj点或直接有边，或最多经v1 v2为中间点时的最短路长(2)02040801520020602540200301880603008515251885015150D(3)02040701520020502540200301870503004815251848015150D(4)(3)DD(5)020336315302002050254033200301833635030048631525184801530403363150D(6)(5)DD作业作业P2568.18.6
