图与网络分析.ppt

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

1、图与网络分析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望图与网络分析 p在现实生活和生产活动中，许多问题都可以用网在现实生活和生产活动中，许多问题都可以用网络模型来描写。如：在现有交通网络中，如何使络模型来描写。如：在现有交通网络中，如何使调运的物资数量多且费用最小等。调运的物资数量多且费用最小等。p网络模型就是一种应用图论的理论与方法解决具网络模型就是一种应用图论的理论与方法解决具有网络性质的管理决策问题的数学模型。有网络性质的管理决策问题的数学模型。p网络

2、模型具有图形直观，方法简便，容易掌握的网络模型具有图形直观，方法简便，容易掌握的特点，广泛地应用在各个领域，尤其是经济活动特点，广泛地应用在各个领域，尤其是经济活动中许多管理决策的优化问题。中许多管理决策的优化问题。2图与网络的基本概念 3图及其分类 p图图是点与线的集合。一个图由一些点及一些点之是点与线的集合。一个图由一些点及一些点之间的联线间的联线(不带箭头或带箭头不带箭头或带箭头)所所组成。组成。p为了区别起见。把两点之间的带箭头的联线称为为了区别起见。把两点之间的带箭头的联线称为边边，带箭头的联线称为，带箭头的联线称为弧弧。p用图来描述事物间的联系，不仅直观清晰，便于用图来描述事物间的

3、联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。间关系的一种工具。4无向图p由点和边组成的图称为由点和边组成的图称为无向图无向图。5无向图6环、多重边、简单图、多重图7点的次8链、圈、连通图9子图10子图v111有向图 p由点和弧组成的图称为由点和弧组成的图称为有向图有向图。12环、多重弧、简单有向图 13点的出次和入次、路14网络的概念 15图的矩阵表示：关联矩阵 16图的矩阵表示：邻接矩阵 17图的矩阵表示：权矩阵 18树与最小树

4、问题 19树的概念和性质 v1v2v3v4v5v64321720树的概念和性质21支撑树 22用破圈法与避圈法求支撑树23最小树 破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。24最小树 5v1v2v3v4v5v6843752618【例【例8.1】用破圈法求下图的最小树。】用破圈法求下图的最小树。最小树长为最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一

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

6、v684375268Min C(T)=1526最小树的寻找方法：矩阵法27矩阵法举例28矩阵法29矩阵法举例30矩阵法举例31最最短短路路问问题题在在实实际际中中具具有有广广泛泛的的应应用用，如如管管道道铺铺设设、线线路路选选择择等等问问题题，还还有有些些如如设设备备更更新新、投投资资等等问问题题也也可可以以归归结结为为求求最最短短路问题路问题 求最短路有两种算法：求最短路有两种算法：一一是是求求从从某某一一点点至至其其它它各各点点之之间间最最短短离离的的狄狄克克斯斯屈屈拉拉(Dijkstra)算法算法 另一种是针对网络中有负权的另一种是针对网络中有负权的逐次逼近法。逐次逼近法。最短路问题，就

7、是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 最短路问题32610123214675811165图图669【例【例8.3】下图中的权】下图中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离最，如何选择一条路线使距离最短，建立该问题的网络数学模型。短，建立该问题的网络数学模型。33【解】【解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，

8、不选择弧不选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：34Dijkstra标号法原理 35Dijkstra标号法原理36Dijkstra算法的具体步骤 37Dijkstra算法的具体步骤386101232146758111659(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 39Dijkstra算法举例40Di

9、jkstra算法举例23718456613410527593468241逐次逼近法 42逐次逼近法43逐次逼近法举例44逐次逼近法举例45逐次逼近法举例46逐次逼近法举例47最短链问题 48最短链问题49最短链问题举例50最短链问题举例51最短链问题举例52最短链问题举例53最短链问题举例54最短链问题举例55网络最大流问题 p所谓所谓最大流量问题最大流量问题就是：给一个带收发点的网络（一般收就是：给一个带收发点的网络（一般收点用点用vt表示，发点用表示，发点用vs表示，其余为中间点），其每条弧表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要的权值称之为容量，在

10、不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。求确定每条弧的流量，得出从发点到收点的最大流量。p在交通运输、物资供应、通讯系统和财政金融等实际工作在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。中，常会遇到这类最大流问题。56网络最大流问题57最大流有关概念58可行流与最大流 59增广链的概念60增广链的概念61截集和截量62截集和截量63截集和截量64满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为称为可行流可行流 发发点点vs流出的流出的总总流量等于流入收点流量等于流入收点vt的的总总流量流量概念回顾

11、65链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链8446

12、9（5）(2)(3)(4)(6)66寻找网络最大流的Ford-Fulkerson标号法 67算法的步骤 68算法的步骤69算法举例70算法举例71算法举例72算法举例73算法举例74算法举例75算法举例76(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的最大流及最大流量的最大流及最大流量77无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已已标号另一端标号

13、另一端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)(13,13)(9,0)(16,13)0,v1,2v4,2v5,2v6,2v2,278(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,179(12,12)(9,7)(20,10)(8,8)(5,4)(8,

14、3)(7,7)(6,6)(14,8)(13,13)(9,3)(16,16)V=290,v1,10v3,5v4,5v5,5v4,180最小费用网络最大流问题 81最小费用最大流问题 82最小费用增广链 83求最小费用流的基本思想 84辅助赋权有向网络的构造方法 85最小费用最大流算法步骤86最小费用最大流算法应用举例 87最小费用最大流算法应用举例88最小费用最大流算法应用举例89最小费用最大流算法应用举例90最小费用最大流算法应用举例91最小费用最大流算法应用举例92最小费用最大流算法应用举例93欧拉图94欧拉链、欧拉圈与欧拉图p欧拉链欧拉链 给定一个连通多重图给定一个连通多重图G，若存在一条

15、链，经过每边一次，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。且仅一次，称这条链为欧拉链。p欧拉圈欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。若存在一个简单圈，过每边一次，称这个圈为欧拉圈。p欧拉图欧拉图 一个具有欧拉圈的图，称为欧拉图。一个具有欧拉圈的图，称为欧拉图。p上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。拉圈。95定理与推论定理与推论p定理定理1 连通多重图连通多重图G 是欧拉图的充要条件是图中的点全是欧拉图的充要条件是图中的点全为偶点。为偶点。p 定理定理2 连通多重图连通多重图G有欧拉链，当且仅当有欧

16、拉链，当且仅当G中恰有两个中恰有两个奇点。奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。96中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一邮递员负责某所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。的总路程最短。p中国邮递员问题的

17、图论语言描述：给定一个连通图，在每中国邮递员问题的图论语言描述：给定一个连通图，在每边上边上ei上赋予一个非负的权上赋予一个非负的权w(ei),要求一个圈（未必是简要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。单的），过每边至少一次，并使圈的总权最小。97中国邮递员问题求解考虑两种情形：考虑两种情形：p如果如果G是欧拉图，则从邮局出发，每边恰好走一是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；p如果如果G不是欧拉图，则某些边必然要重复走，我不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以们当然要

18、求重复走过的边的总长最小。我们可以用用“奇偶点图上作业法奇偶点图上作业法”解决这一问题。解决这一问题。98“奇偶点图上作业法”相关定理99奇偶点图上作业法100奇偶点图上作业法举例101奇偶点图上作业法举例102奇偶点图上作业法举例103奇偶点图上作业法举例104奇偶点图上作业法举例105【例】求解下图的中国邮路问题【例】求解下图的中国邮路问题 35v1v2v4v5v6v74752618v341奇偶点图上作业法举例1065v1v2v4v5v6v743752618v34141【解】最优解如下图【解】最优解如下图14上图为最短欧拉回路，重复经过了上图为最短欧拉回路，重复经过了1，2和和6，7两条边两条边107