《第6章图与网络分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第6章图与网络分析优秀PPT.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 图与网络分析现在学习的是第1页，共105页2图及其分类 p图图是点与线的集合。一个图由一些点及一些点之是点与线的集合。一个图由一些点及一些点之间的联线间的联线(不带箭头或带箭头不带箭头或带箭头)所所组成。组成。p为了区别起见。把两点之间的不带箭头的连线称为了区别起见。把两点之间的不带箭头的连线称为为边边，带箭头的连线称为，带箭头的连线称为弧弧。p用图来描述事物间的联系，不仅直观清晰，便于用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之比例和曲直。总之，这里所讲的图是反
2、映对象之间关系的一种工具。间关系的一种工具。2022/12/5现在学习的是第2页，共105页3无向图p由点和边组成的图称为由点和边组成的图称为无向图无向图。2022/12/5现在学习的是第3页，共105页4无向图2022/12/5现在学习的是第4页，共105页5环、多重边、简单图、多重图2022/12/5现在学习的是第5页，共105页6点的次2022/12/5现在学习的是第6页，共105页7链、圈、连通图2022/12/5现在学习的是第7页，共105页8子图2022/12/5现在学习的是第8页，共105页9子图v12022/12/5现在学习的是第9页，共105页10有向图 p由点和弧组成的图称
3、为由点和弧组成的图称为有向图有向图。2022/12/5现在学习的是第10页，共105页11环、多重弧、简单有向图 2022/12/5现在学习的是第11页，共105页12点的出次和入次、路2022/12/5现在学习的是第12页，共105页13网络的概念 2022/12/5现在学习的是第13页，共105页14图的矩阵表示：关联矩阵 2022/12/5现在学习的是第14页，共105页15图的矩阵表示：邻接矩阵 2022/12/5现在学习的是第15页，共105页16图的矩阵表示：权矩阵 2022/12/5现在学习的是第16页，共105页17树与最小树问题 2022/12/5现在学习的是第17页，共10
4、5页18树的概念和性质 v1v2v3v4v5v6432172022/12/5现在学习的是第18页，共105页19树的概念和性质2022/12/5现在学习的是第19页，共105页20支撑树 2022/12/5现在学习的是第20页，共105页21用破圈法与避圈法求支撑树2022/12/5现在学习的是第21页，共105页22最小树 破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。2022/12/5现在学习的是第22页，共105页23最小树 5v1v2v3v4v5v6843752618【例例8.1】用破圈法求下图的最小树。用破圈法求下图的最小树。最小树长为最小树
5、长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同中任意一条边。最小部分树有可能不唯一，但最小树的长度相同 2022/12/5现在学习的是第23页，共105页24避圈法避圈法：取：取图图G的的n个孤立点个孤立点v1，v2，vn作为一个支撑图，从最作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521在上图中，如果添加边在上图中
6、，如果添加边v1,v2就形成圈就形成圈v1,v2,v4，这时就应避开添，这时就应避开添加边加边v1,v2，添加下一条最短边，添加下一条最短边v3,v6。破圈法和避圈法得到树的形状。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=152022/12/5现在学习的是第24页，共105页25最小树的寻找方法：矩阵法2022/12/5现在学习的是第25页，共105页26矩阵法举例2022/12/5现在学习的是第26页，共105页27矩阵法2022/12/5现在学习的是第27页，共105页28矩阵法举
7、例2022/12/5现在学习的是第28页，共105页29矩阵法举例2022/12/5现在学习的是第29页，共105页30最最短短路路问问题题在在实实际际中中具具有有广广泛泛的的应应用用，如如管管道道铺铺设设、线线路路选选择择等等问问题，还有些如设备更新、投资等问题也可以归结为求最短路问题题，还有些如设备更新、投资等问题也可以归结为求最短路问题 求最短路有两种算法：求最短路有两种算法：一是求从某一点至其它各点之间最短离的一是求从某一点至其它各点之间最短离的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一种是针对网络中有负权的另一种是针对网络中有负权的逐次逼近法。逐次逼近法。最短路问题，就是
8、从给定的网络图中找出一点到各点或任意两点之间距离最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路最短的一条路 最短路问题2022/12/5现在学习的是第30页，共105页31610123214675811165图图669【例例8.3】下图中的权下图中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路修一条公路或架设一条高压线到或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网，如何选择一条路线使距离最短，建立该问题的网络数学模型。络数学模型。2022/12/5现在学习的是第31页，共105页32【解解】设设x
9、ij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不选择弧，不选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：2022/12/5现在学习的是第32页，共105页33Dijkstra标号法原理 2022/12/5现在学习的是第33页，共105页34Dijkstra标号法原理2022/12/5现在学习的是第34页，共105页35Dijkstra算法的具体步骤 2022/12/5现在学习的是第35页，共105页36Dijkstra算法的具体步骤2022/12/5现在学习的是第36页，共105页3761012321467581
10、11659(6,v1)(12,v1)(16,v3)(18,v3)(29,v5)【例例8.3】用用Dijkstra算法求下图所示算法求下图所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 2022/12/5现在学习的是第37页，共105页38Dijkstra算法举例2022/12/5现在学习的是第38页，共105页39Dijkstra算法举例2371845661341052759346822022/12/5现在学习的是第39页，共105页40逐次逼近法 2022/12/5现在学习的
11、是第40页，共105页41逐次逼近法2022/12/5现在学习的是第41页，共105页42逐次逼近法举例2022/12/5现在学习的是第42页，共105页43逐次逼近法举例2022/12/5现在学习的是第43页，共105页44逐次逼近法举例2022/12/5现在学习的是第44页，共105页45逐次逼近法举例2022/12/5现在学习的是第45页，共105页46最短链问题 2022/12/5现在学习的是第46页，共105页47最短链问题2022/12/5现在学习的是第47页，共105页48最短链问题举例2022/12/5现在学习的是第48页，共105页49最短链问题举例2022/12/5现在学习
12、的是第49页，共105页50最短链问题举例2022/12/5现在学习的是第50页，共105页51最短链问题举例2022/12/5现在学习的是第51页，共105页52最短链问题举例2022/12/5现在学习的是第52页，共105页53最短链问题举例2022/12/5现在学习的是第53页，共105页54网络最大流问题 p所谓所谓最大流量问题最大流量问题就是：给一个带收发点的网络（一般收点就是：给一个带收发点的网络（一般收点用用vt表示，发点用表示，发点用vs表示，其余为中间点），其每条弧的权值称表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的之为容量，
13、在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。流量，得出从发点到收点的最大流量。p在交通运输、物资供应、通讯系统和财政金融等实际工作中，常在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。会遇到这类最大流问题。2022/12/5现在学习的是第54页，共105页55网络最大流问题2022/12/5现在学习的是第55页，共105页56最大流有关概念2022/12/5现在学习的是第56页，共105页57可行流与最大流 2022/12/5现在学习的是第57页，共105页58增广链的概念2022/12/5现在学习的是第58页，共105页59增
14、广链的概念2022/12/5现在学习的是第59页，共105页60截集和截量2022/12/5现在学习的是第60页，共105页61截集和截量2022/12/5现在学习的是第61页，共105页62截集和截量2022/12/5现在学习的是第62页，共105页63满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为称为可行流可行流 发发点点vs流出的流出的总总流量等于流入收点流量等于流入收点vt的的总总流量流量概念回顾2022/12/5现在学习的是第63页，共105页64链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）
15、称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)2022/12/5现在学习的是第64页，共105页65寻找网络最大流的Ford-
16、Fulkerson标号法 2022/12/5现在学习的是第65页，共105页66算法的步骤 2022/12/5现在学习的是第66页，共105页67算法的步骤2022/12/5现在学习的是第67页，共105页68算法举例2022/12/5现在学习的是第68页，共105页69算法举例2022/12/5现在学习的是第69页，共105页70算法举例2022/12/5现在学习的是第70页，共105页71算法举例2022/12/5现在学习的是第71页，共105页72算法举例2022/12/5现在学习的是第72页，共105页73算法举例2022/12/5现在学习的是第73页，共105页74算法举例2022/
17、12/5现在学习的是第74页，共105页75(14，10)(8，6)(5，3)(6，6)(3，3)(8，7)(3，0)(6，6)(3，1)(10，3)(4，1)(7，7)【例例8.7】求下图发点求下图发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量2022/12/5现在学习的是第75页，共105页76无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另已标号另一端一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj就可标号（就可标号（Cijfij）【例例8.
18、8】求下图求下图v1到则到则v7标的最大流标的最大流(12,10)(9,6)(20,10)(8,8)(5,2)(8,3)(7,7)(6,6)(14,5)(13,13)(9,0)(16,13)0,v1,2v4,2v5,2v6,2v2,2现在学习的是第76页，共105页77(12,12)(9,6)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,7)(13,13)(9,2)(16,15)0,v1,3v4,3v5,3v6,12022/12/5现在学习的是第77页，共105页78(12,12)(9,7)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,8)(
19、13,13)(9,3)(16,16)V=290,v1,10v3,5v4,5v5,5v4,1现在学习的是第78页，共105页79最小费用网络最大流问题 2022/12/5现在学习的是第79页，共105页80最小费用最大流问题 2022/12/5现在学习的是第80页，共105页81最小费用增广链 2022/12/5现在学习的是第81页，共105页82求最小费用流的基本思想 2022/12/5现在学习的是第82页，共105页83辅助赋权有向网络的构造方法 2022/12/5现在学习的是第83页，共105页84最小费用最大流算法步骤2022/12/5现在学习的是第84页，共105页85最小费用最大流算
20、法应用举例 2022/12/5现在学习的是第85页，共105页86最小费用最大流算法应用举例2022/12/5现在学习的是第86页，共105页87最小费用最大流算法应用举例2022/12/5现在学习的是第87页，共105页88最小费用最大流算法应用举例2022/12/5现在学习的是第88页，共105页89最小费用最大流算法应用举例2022/12/5现在学习的是第89页，共105页90最小费用最大流算法应用举例2022/12/5现在学习的是第90页，共105页91最小费用最大流算法应用举例2022/12/5现在学习的是第91页，共105页92欧拉图2022/12/5现在学习的是第92页，共105
21、页93欧拉链、欧拉圈与欧拉图p欧拉链欧拉链 给定一个连通多重图给定一个连通多重图G，若存在一条链，经过每边一次且仅，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。一次，称这条链为欧拉链。p欧拉圈欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。若存在一个简单圈，过每边一次，称这个圈为欧拉圈。p欧拉图欧拉图 一个具有欧拉圈的图，称为欧拉图。一个具有欧拉圈的图，称为欧拉图。p上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。2022/12/5现在学习的是第93页，共105页94定理与推论定理与推论p定理定理1 连通多重图连通多
22、重图G 是欧拉图的充要条件是图中的点全是欧拉图的充要条件是图中的点全为偶点。为偶点。p 定理定理2 连通多重图连通多重图G有欧拉链，当且仅当有欧拉链，当且仅当G中恰有两个中恰有两个奇点。奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。2022/12/5现在学习的是第94页，共105页95中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一邮递员负责某街所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的
23、所有区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走的总路街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。程最短。p中国邮递员问题的图论语言描述：给定一个连通图，在每边上中国邮递员问题的图论语言描述：给定一个连通图，在每边上ei上赋予一个非负的权上赋予一个非负的权w(ei),要求一个圈（未必是简单的），要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。过每边至少一次，并使圈的总权最小。2022/12/5现在学习的是第95页，共105页96中国邮递员问题求解考虑两种情形：考虑两种情形：p如果如果G是欧拉图，则从邮局出发，每
24、边恰好走一是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；p如果如果G不是欧拉图，则某些边必然要重复走，我不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以们当然要求重复走过的边的总长最小。我们可以用用“奇偶点图上作业法奇偶点图上作业法”解决这一问题。解决这一问题。2022/12/5现在学习的是第96页，共105页97“奇偶点图上作业法”相关定理2022/12/5现在学习的是第97页，共105页98奇偶点图上作业法2022/12/5现在学习的是第98页，共105页99奇偶点图上作业法举例2022/12/5现在学习的
25、是第99页，共105页100奇偶点图上作业法举例2022/12/5现在学习的是第100页，共105页101奇偶点图上作业法举例2022/12/5现在学习的是第101页，共105页102奇偶点图上作业法举例2022/12/5现在学习的是第102页，共105页103奇偶点图上作业法举例2022/12/5现在学习的是第103页，共105页104【例例】求解下图的中国邮路问题求解下图的中国邮路问题 35v1v2v4v5v6v74752618v341奇偶点图上作业法举例2022/12/5现在学习的是第104页，共105页1055v1v2v4v5v6v743752618v34141【解解】最优解如下图最优解如下图14上图为最短欧拉回路，重复经过了上图为最短欧拉回路，重复经过了1，2和和6，7两条边两条边2022/12/5现在学习的是第105页，共105页