第6章图与网络分析PPT讲稿.ppt

《第6章图与网络分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第6章图与网络分析PPT讲稿.ppt（105页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第6章 图与网络分析第1页，共105页，编辑于2022年，星期二2图及其分类 p图图是点与线的集合。一个图由一些点及一些点之是点与线的集合。一个图由一些点及一些点之间的联线间的联线(不带箭头或带箭头不带箭头或带箭头)所所组成。组成。p为了区别起见。把两点之间的不带箭头的连线称为了区别起见。把两点之间的不带箭头的连线称为为边边，带箭头的连线称为，带箭头的连线称为弧弧。p用图来描述事物间的联系，不仅直观清晰，便于用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之比例和曲直。总之，这

2、里所讲的图是反映对象之间关系的一种工具。间关系的一种工具。2022/9/21第2页，共105页，编辑于2022年，星期二3无向图p由点和边组成的图称为由点和边组成的图称为无向图无向图。2022/9/21第3页，共105页，编辑于2022年，星期二4无向图2022/9/21第4页，共105页，编辑于2022年，星期二5环、多重边、简单图、多重图2022/9/21第5页，共105页，编辑于2022年，星期二6点的次2022/9/21第6页，共105页，编辑于2022年，星期二7链、圈、连通图2022/9/21第7页，共105页，编辑于2022年，星期二8子图2022/9/21第8页，共105页，编

3、辑于2022年，星期二9子图v12022/9/21第9页，共105页，编辑于2022年，星期二10有向图 p由点和弧组成的图称为由点和弧组成的图称为有向图有向图。2022/9/21第10页，共105页，编辑于2022年，星期二11环、多重弧、简单有向图 2022/9/21第11页，共105页，编辑于2022年，星期二12点的出次和入次、路2022/9/21第12页，共105页，编辑于2022年，星期二13网络的概念 2022/9/21第13页，共105页，编辑于2022年，星期二14图的矩阵表示：关联矩阵 2022/9/21第14页，共105页，编辑于2022年，星期二15图的矩阵表示：邻接矩

4、阵 2022/9/21第15页，共105页，编辑于2022年，星期二16图的矩阵表示：权矩阵 2022/9/21第16页，共105页，编辑于2022年，星期二17树与最小树问题 2022/9/21第17页，共105页，编辑于2022年，星期二18树的概念和性质 v1v2v3v4v5v6432172022/9/21第18页，共105页，编辑于2022年，星期二19树的概念和性质2022/9/21第19页，共105页，编辑于2022年，星期二20支撑树 2022/9/21第20页，共105页，编辑于2022年，星期二21用破圈法与避圈法求支撑树2022/9/21第21页，共105页，编辑于2022

5、年，星期二22最小树 破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。2022/9/21第22页，共105页，编辑于2022年，星期二23最小树 5v1v2v3v4v5v6843752618【例例8.1】用破圈法求下图的最小树。用破圈法求下图的最小树。最小树长为最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同中任意一条边。最小部分树有可能不唯一，但最小树的长度相同 2022/9/21第

6、23页，共105页，编辑于2022年，星期二24避圈法避圈法：取：取图图G的的n个孤立点个孤立点v1，v2，vn作为一个支撑图，从最作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521在上图中，如果添加边在上图中，如果添加边v1,v2就形成圈就形成圈v1,v2,v4，这时就应避开添加，这时就应避开添加边边v1,v2，添加下一条最短边，添加下一条最短边v3,v6。破圈法和避圈法得到树的形状可能。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等不一样，但最小树的长度相等 5v1v3

7、v515v2v4v684375268Min C(T)=152022/9/21第24页，共105页，编辑于2022年，星期二25最小树的寻找方法：矩阵法2022/9/21第25页，共105页，编辑于2022年，星期二26矩阵法举例2022/9/21第26页，共105页，编辑于2022年，星期二27矩阵法2022/9/21第27页，共105页，编辑于2022年，星期二28矩阵法举例2022/9/21第28页，共105页，编辑于2022年，星期二29矩阵法举例2022/9/21第29页，共105页，编辑于2022年，星期二30最最短短路路问问题题在在实实际际中中具具有有广广泛泛的的应应用用，如如管管

8、道道铺铺设设、线线路路选选择择等等问问题题，还还有有些如设备更新、投资等问题也可以归结为求最短路问题些如设备更新、投资等问题也可以归结为求最短路问题 求最短路有两种算法：求最短路有两种算法：一一是是求求从从某某一一点点至至其其它它各各点点之之间间最最短短离离的的狄狄克克斯斯屈屈拉拉(Dijkstra)算算法法 另一种是针对网络中有负权的另一种是针对网络中有负权的逐次逼近法。逐次逼近法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路短的一条路 最短路问题2022/9/21第30页，共105页，编辑于2

9、022年，星期二31610123214675811165图图669【例例8.3】下图中的权下图中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路修一条公路或架设一条高压线到或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题，如何选择一条路线使距离最短，建立该问题的网络数学模型。的网络数学模型。2022/9/21第31页，共105页，编辑于2022年，星期二32【解解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不选择弧，不选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短

10、路问题的网络模型：2022/9/21第32页，共105页，编辑于2022年，星期二33Dijkstra标号法原理 2022/9/21第33页，共105页，编辑于2022年，星期二34Dijkstra标号法原理2022/9/21第34页，共105页，编辑于2022年，星期二35Dijkstra算法的具体步骤 2022/9/21第35页，共105页，编辑于2022年，星期二36Dijkstra算法的具体步骤2022/9/21第36页，共105页，编辑于2022年，星期二376101232146758111659(6,v1)(12,v1)(16,v3)(18,v3)(29,v5)【例例8.3】用用D

11、ijkstra算法求下图所示算法求下图所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 2022/9/21第37页，共105页，编辑于2022年，星期二38Dijkstra算法举例2022/9/21第38页，共105页，编辑于2022年，星期二39Dijkstra算法举例2371845661341052759346822022/9/21第39页，共105页，编辑于2022年，星期二40逐次逼近法 2022/9/21第40页，共105页，编辑于2022年，星期二41逐次逼近法202

12、2/9/21第41页，共105页，编辑于2022年，星期二42逐次逼近法举例2022/9/21第42页，共105页，编辑于2022年，星期二43逐次逼近法举例2022/9/21第43页，共105页，编辑于2022年，星期二44逐次逼近法举例2022/9/21第44页，共105页，编辑于2022年，星期二45逐次逼近法举例2022/9/21第45页，共105页，编辑于2022年，星期二46最短链问题 2022/9/21第46页，共105页，编辑于2022年，星期二47最短链问题2022/9/21第47页，共105页，编辑于2022年，星期二48最短链问题举例2022/9/21第48页，共105页

13、，编辑于2022年，星期二49最短链问题举例2022/9/21第49页，共105页，编辑于2022年，星期二50最短链问题举例2022/9/21第50页，共105页，编辑于2022年，星期二51最短链问题举例2022/9/21第51页，共105页，编辑于2022年，星期二52最短链问题举例2022/9/21第52页，共105页，编辑于2022年，星期二53最短链问题举例2022/9/21第53页，共105页，编辑于2022年，星期二54网络最大流问题 p所谓所谓最大流量问题最大流量问题就是：给一个带收发点的网络（一般收点用就是：给一个带收发点的网络（一般收点用vt表表示，发点用示，发点用vs表

14、示，其余为中间点），其每条弧的权值称之为表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的流容量，在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。量，得出从发点到收点的最大流量。p在交通运输、物资供应、通讯系统和财政金融等实际工作中，常在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。会遇到这类最大流问题。2022/9/21第54页，共105页，编辑于2022年，星期二55网络最大流问题2022/9/21第55页，共105页，编辑于2022年，星期二56最大流有关概念2022/9/21第56

15、页，共105页，编辑于2022年，星期二57可行流与最大流 2022/9/21第57页，共105页，编辑于2022年，星期二58增广链的概念2022/9/21第58页，共105页，编辑于2022年，星期二59增广链的概念2022/9/21第59页，共105页，编辑于2022年，星期二60截集和截量2022/9/21第60页，共105页，编辑于2022年，星期二61截集和截量2022/9/21第61页，共105页，编辑于2022年，星期二62截集和截量2022/9/21第62页，共105页，编辑于2022年，星期二63满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为称

16、为可行流可行流 发发点点vs流出的流出的总总流量等于流入收点流量等于流入收点vt的的总总流量流量概念回顾2022/9/21第63页，共105页，编辑于2022年，星期二64链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt

17、的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)2022/9/21第64页，共105页，编辑于2022年，星期二65寻找网络最大流的Ford-Fulkerson标号法 2022/9/21第65页，共105页，编辑于2022年，星期二66算法的步骤 2022/9/21第66页，共105页，编辑于2022年，星期二67算法的步骤2022/9/21第67页，共105页，编辑于2022年，星期二68算法举例2022/9/21第68页，共105页，编辑于

18、2022年，星期二69算法举例2022/9/21第69页，共105页，编辑于2022年，星期二70算法举例2022/9/21第70页，共105页，编辑于2022年，星期二71算法举例2022/9/21第71页，共105页，编辑于2022年，星期二72算法举例2022/9/21第72页，共105页，编辑于2022年，星期二73算法举例2022/9/21第73页，共105页，编辑于2022年，星期二74算法举例2022/9/21第74页，共105页，编辑于2022年，星期二75(14，10)(8，6)(5，3)(6，6)(3，3)(8，7)(3，0)(6，6)(3，1)(10，3)(4，1)(7，

19、7)【例例8.7】求下图发点求下图发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量2022/9/21第75页，共105页，编辑于2022年，星期二76无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号已标号另一端另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj就可标号（就可标号（Cijfij）【例例8.8】求下图求下图v1到则到则v7标的最大流标的最大流(12,10)(9,6)(20,10)(8,8)(5,2)(8,3)(7,7)(6,6)(14,5)

20、(13,13)(9,0)(16,13)0,v1,2v4,2v5,2v6,2v2,2第76页，共105页，编辑于2022年，星期二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/9/21第77页，共105页，编辑于2022年，星期二78(12,12)(9,7)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,8)(13,13)(9,3)(16,16)V=290,v1,10v3,5v4,5v5,5v4,1第78页，共105页，编辑于202

21、2年，星期二79最小费用网络最大流问题 2022/9/21第79页，共105页，编辑于2022年，星期二80最小费用最大流问题 2022/9/21第80页，共105页，编辑于2022年，星期二81最小费用增广链 2022/9/21第81页，共105页，编辑于2022年，星期二82求最小费用流的基本思想 2022/9/21第82页，共105页，编辑于2022年，星期二83辅助赋权有向网络的构造方法 2022/9/21第83页，共105页，编辑于2022年，星期二84最小费用最大流算法步骤2022/9/21第84页，共105页，编辑于2022年，星期二85最小费用最大流算法应用举例 2022/9/

22、21第85页，共105页，编辑于2022年，星期二86最小费用最大流算法应用举例2022/9/21第86页，共105页，编辑于2022年，星期二87最小费用最大流算法应用举例2022/9/21第87页，共105页，编辑于2022年，星期二88最小费用最大流算法应用举例2022/9/21第88页，共105页，编辑于2022年，星期二89最小费用最大流算法应用举例2022/9/21第89页，共105页，编辑于2022年，星期二90最小费用最大流算法应用举例2022/9/21第90页，共105页，编辑于2022年，星期二91最小费用最大流算法应用举例2022/9/21第91页，共105页，编辑于20

23、22年，星期二92欧拉图2022/9/21第92页，共105页，编辑于2022年，星期二93欧拉链、欧拉圈与欧拉图p欧拉链欧拉链 给定一个连通多重图给定一个连通多重图G，若存在一条链，经过每边一次且仅，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。一次，称这条链为欧拉链。p欧拉圈欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。若存在一个简单圈，过每边一次，称这个圈为欧拉圈。p欧拉图欧拉图 一个具有欧拉圈的图，称为欧拉图。一个具有欧拉圈的图，称为欧拉图。p上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。2022/9/21

24、第93页，共105页，编辑于2022年，星期二94定理与推论定理与推论p定理定理1 连通多重图连通多重图G 是欧拉图的充要条件是图中的点全是欧拉图的充要条件是图中的点全为偶点。为偶点。p 定理定理2 连通多重图连通多重图G有欧拉链，当且仅当有欧拉链，当且仅当G中恰有两个中恰有两个奇点。奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。2022/9/21第94页，共105页，编辑于2022年，星期二95中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一

25、邮递员负责某街区所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。再回到邮局，他应如何安排投递路线，使所走的总路程最短。p中国邮递员问题的图论语言描述：给定一个连通图，在每边上中国邮递员问题的图论语言描述：给定一个连通图，在每边上ei上赋予一个非负的权上赋予一个非负的权w(ei),要求一个圈（未必是简单的），过每要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。边至少一次，并使圈的总权最小。2022/9/21第95

26、页，共105页，编辑于2022年，星期二96中国邮递员问题求解考虑两种情形：考虑两种情形：p如果如果G是欧拉图，则从邮局出发，每边恰好走一是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；p如果如果G不是欧拉图，则某些边必然要重复走，我不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以们当然要求重复走过的边的总长最小。我们可以用用“奇偶点图上作业法奇偶点图上作业法”解决这一问题。解决这一问题。2022/9/21第96页，共105页，编辑于2022年，星期二97“奇偶点图上作业法”相关定理2022/9/21第97页，共

27、105页，编辑于2022年，星期二98奇偶点图上作业法2022/9/21第98页，共105页，编辑于2022年，星期二99奇偶点图上作业法举例2022/9/21第99页，共105页，编辑于2022年，星期二100奇偶点图上作业法举例2022/9/21第100页，共105页，编辑于2022年，星期二101奇偶点图上作业法举例2022/9/21第101页，共105页，编辑于2022年，星期二102奇偶点图上作业法举例2022/9/21第102页，共105页，编辑于2022年，星期二103奇偶点图上作业法举例2022/9/21第103页，共105页，编辑于2022年，星期二104【例例】求解下图的中国邮路问题求解下图的中国邮路问题 35v1v2v4v5v6v74752618v341奇偶点图上作业法举例2022/9/21第104页，共105页，编辑于2022年，星期二1055v1v2v4v5v6v743752618v34141【解解】最优解如下图最优解如下图14上图为最短欧拉回路，重复经过了上图为最短欧拉回路，重复经过了1，2和和6，7两条边两条边2022/9/21第105页，共105页，编辑于2022年，星期二