《《运筹学教程》胡云权 第五版 第五章 图与网络分析》由会员分享，可在线阅读，更多相关《《运筹学教程》胡云权 第五版 第五章 图与网络分析（56页珍藏版）》请在金锄头文库上搜索。
1、第五章 图论与网络分析学习目标ABCDACBD图论起源哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？图的基本概念哈密尔顿回路问题：环球旅行遊戏欧拉回路：每边经过一次且仅一次的回路 哈密尔顿回路：每个点经过一次且仅一次的回路问题：游戏者从任一城市出发，寻找一条可经过每 个城市一次且仅一次，在回到原出发点的路?图的基本概念1234567 8 910111213 14151617181920定义1：由点和边组成，记作G=(V，E)，其中 V=v1，v2，vn为结点的集合，E=e1，e2，em为边的集合。 点表
2、示研究对象边表示表示研究对象之间的特定关系1. 图图的基本概念注意：上面定义的图区别于几何学中的图。几何学中 ，图中点的位置、线的长度和斜率等都十分重要，而这 里只关心图中有多少点以及哪些点之间有线相连。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可记作：图的基
3、本概念端点，相邻，关联边图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5图51环，多重边，简单图 一条边的两个端点相同，称此边为环，e1； 两个点之间多于一条，称为多重边，e4和e52、图的分类定义2：无环、无多重边的图称作简单图。含有多重边的图为多重图。图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边 称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类图的基本概念图的基本概念定义3：每一对顶点间都有边相连的无向简单图，称为完全图。有n个顶点的无向完全图记为Kn。2、图的分类定义4：图
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)。v3e7e4e8e5e6e1e2e3v1v2v4v5图51图5-1中，d(v1)，d(v3)=5，d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点， 次为0的点称作孤立点。 次为1的点称作悬挂点，连接悬挂点的边为悬挂边。 图的次：各点的次之和。 有向图中顶点的次？定理1：任何图中，顶点次数的
5、总和等于边数的2倍 。 定理2： 任何图中，次为奇数的顶点为偶数个。4、子图、支撑子图图G=(V, E)和G =(V ,E )，若V V，E E，则称G 为G的 子图。特别地，若V =V 且E E，则称G 为G的支撑子图 。 G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2图的基本概念5、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称 为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423图的基本概念v1v2v3v4v56、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向
6、图：图的基本概念没有重复点和重复边的链为初等链。初等圈7、连通图定义10：任意两点之间至少存在一条链的图称为连通图 ，否则称为不连通图。G1G2G1为不连通图， 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其他树支撑树最小支撑树【例】今有煤气站A，将给一居民区供应煤气，居民区各 用户所
7、在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222545 2634531最小支撑树问题1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最 少边数的一种图形。3、边数 = 顶点数 1。1、树连通且无圈的无向图(A)(B)(C)树的性质：判断下面图形哪个是树：最小支撑树问题若一个图 G =（V , E）的支撑子 图 T=（V , E） 构成树，则称 T 为 G的支撑树，又称生成树、部分树。2、图的支撑树(G)(G1)(G2)(G3)(G
8、4)最小支撑树问题【例】 某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？【解 】该问题实为求图的支撑 树问题，共需铺4条路 。v1v2v3v4v5图的支撑树的应用举例v1v2v3v4v555.57.53.54 23最小支撑树问题问题：求网络的支撑树，使其权和最小。3、最小支撑树问题算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数） 。【例】 求上例中的最小支撑树【解 】3v12v4v545 v23.5v3最小支撑树问题55.5v1v2v3v4v57.53.54 23算
9、法2（破圈法）：在图中找圈，并删除其中权数最大 的边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.54 23最小支撑树问题3、最小支撑树问题算法2（破圈法）：在图中找圈，并删除其中权数最大 的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树问题55.5v1v2v3v4v53.54 235v1v2v3v4v53.54 23最小支撑树问题3、最小支撑树问题算法2（破圈法）：在图中找圈，并删除其中权数最大 的边。如此进行下去，直至图中不存在圈。算法2（破圈法）：在图中找圈，并删除其中权数最大 的边。如此进行下去，直至图中不存在圈。最小支撑树问题3、最小支撑树
10、问题5v1v2v3v4v53.5 23例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222545 2634531最小支撑树问题例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222245 2634531最小支撑树问题例今有煤气站A，将给一居
11、民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225 2634531最小支撑树问题例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531最小支撑树问题例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需
12、 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531最小支撑树问题例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。I ABCDEFGHJKS222222234531最小支撑树问题例今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的
13、总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元最小支撑树问题案例分析：默登公司的联网问题默登（Modern）公司的管理层决定铺设最先进的光纤网 络，为它的主要中心之间提供高速通信。图1中的节点显示 了该公司主要中心的分布图。虚线是铺设光缆可能的位置。 每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？ ABCEGFD2527457 13144图1 光缆铺设费用图最小支撑树问题ABCEGFD225131图 1 光缆铺设最小费用图案例分析：默登公司的联网问题最小支撑树问题问题描述：设G=(V,E)为连通图，图
14、中各边(vi，vj)有权 数lij（lij=表示vi、vj 间无边，vs、vt为图中任意两点，求 一条道路 ，使从vs到vt的所有路中总权数最小。v2v1v3v4v5v6v7v8v9 163222266133101044【例】 求网络中v1到v9的最短路最短路问题解法1：Dijkstra（狄克斯拉）标号法基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。最短路问题10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 给起点v1标号0, v1(3) 考虑所有这样的边vi ,
15、vj，其中viVA， vjVB，挑选 其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号(4) 重复(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，则dn即为 v1 vn的最短距离，反向追踪可求出最短路
16、。步骤 ： (2) 把顶点集V分成VA：已标号点集VB：未标号点集10v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v91632222661331044
