《图与网络分析》PPT课件

1、运筹学Operations Research图与网络分析 p在现实生活和消费活动中，许多问题都可以用网在现实生活和消费活动中，许多问题都可以用网络模型来描写。如：在现有交通网络中，如何使络模型来描写。如：在现有交通网络中，如何使调运的物资数量多且费用最小等。调运的物资数量多且费用最小等。p网络模型就是一种运用图论的实际与方法处理具网络模型就是一种运用图论的实际与方法处理具有网络性质的管理决策问题的数学模型。有网络性质的管理决策问题的数学模型。p网络模型具有图形直观，方法简便，容易掌握的网络模型具有图形直观，方法简便，容易掌握的特点，广泛地运用在各个领域，尤其是经济活动特点，广泛地运用在各个领域

2、，尤其是经济活动中许多管理决策的优化问题。中许多管理决策的优化问题。图与网络的根本概念 图及其分类 p图是点与线的集合。一个图由一些点及一些点之图是点与线的集合。一个图由一些点及一些点之间的联线间的联线(不带箭头或带箭头不带箭头或带箭头)所组成。所组成。p为了区别起见。把两点之间的带箭头的联线称为为了区别起见。把两点之间的带箭头的联线称为边，带箭头的联线称为弧。边，带箭头的联线称为弧。p用图来描画事物间的联络，不仅直观明晰，便于用图来描画事物间的联络，不仅直观明晰，便于统观全局，而且网络图的画法简便，不用拘泥于统观全局，而且网络图的画法简便，不用拘泥于比例和曲直。总之，这里所讲的图是反映对象之

3、比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。间关系的一种工具。无向图p由点和边组成的图称为无向图。由点和边组成的图称为无向图。无向图环、多重边、简单图、多重图点的次链、圈、连通图子图子图 v1有向图 p由点和弧组成的图称为有向图。由点和弧组成的图称为有向图。 环、多重弧、简单有向图 点的出次和入次 、路网络的概念 图的矩阵表示 ：关联矩阵 图的矩阵表示 ：邻接矩阵 图的矩阵表示 ：权矩阵 NoImage树与最小树问题 树的概念和性质 v1v2v3v4v5v643217树的概念和性质支撑树 用破圈法与避圈法求支撑树最小树 破圈法：任取一圈，去掉圈中最长边，直到无圈。破圈法：任取一

4、圈，去掉圈中最长边，直到无圈。最小树 5v1v2v3v4v5v6843752618【例【例8.1】用破圈法求以下图的最小树。】用破圈法求以下图的最小树。 最小树长为最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个一样的最长边时，不能同时都去掉，只能去当一个圈中有多个一样的最长边时，不能同时都去掉，只能去掉其中恣意一条边。最小部分树有能够不独一，但最小树的长掉其中恣意一条边。最小部分树有能够不独一，但最小树的长度一样度一样 避圈法：取图避圈法：取图G的的n个孤立点个孤立点v1，v2， vn作为一个支撑作为一个支撑图，从最短边开场往支撑图中添加，见圈逃避，直到连通有图，从最短边开场

5、往支撑图中添加，见圈逃避，直到连通有n1条边条边 v1v2v3v4v5v643521在上图中，假设添加边在上图中，假设添加边v1, v2就构成圈就构成圈v1, v2, v4，这时就，这时就应避开添加边应避开添加边v1, v2，添加下一条最短边，添加下一条最短边v3, v6。破圈法和避。破圈法和避圈法得到树的外形能够不一样，但最小树的长度相等圈法得到树的外形能够不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=15最小树的寻觅方法：矩阵法矩阵法举例矩阵法矩阵法举例矩阵法举例最短路问题在实践中具有广泛的运用，如管道铺设、线路选择最短路问题在实践中具有广泛的

6、运用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 求最短路有两种算法：求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法算法 另一种是针对网络中有负权的逐次逼近法。另一种是针对网络中有负权的逐次逼近法。最短路问题，就是从给定的网络图中找出一点到各点或恣意两最短路问题，就是从给定的网络图中找出一点到各点或恣意两点之间间隔最短的一条路点之间间隔最短的一条路 最短路问题610123214675811165图图669【

7、例【例8.3】以下图中的权】以下图中的权cij表示表示vi到到vj的间隔费用、时间，从的间隔费用、时间，从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条道路使间，如何选择一条道路使间隔最短，建立该问题的网络数学模型。隔最短，建立该问题的网络数学模型。【解】【解】 设设xij为选择弧为选择弧(i，j)的形状变量，选择弧的形状变量，选择弧(i，j)时时xij1，不选择弧不选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：( , )12( , )( , )57131467min102,3,610( , )ijiji jEijkii j

8、Ek iEijZc xxxxxxixxxi jE或1，Dijkstra标号法原理 Dijkstra标号法原理Dijkstra算法的详细步骤 Dijkstra算法的详细步骤6101232146758111659(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 Dijkstra算法举例Dijkstra算法举例237184566134105275

9、934682逐次逼近法 逐次逼近法逐次逼近法举例逐次逼近法举例逐次逼近法举例逐次逼近法举例最短链问题 最短链问题最短链问题举例最短链问题举例 最短链问题举例最短链问题举例最短链问题举例最短链问题举例网络最大流问题 p所谓最大流量问题就是：给一个带收发点的网络普通所谓最大流量问题就是：给一个带收发点的网络普通收点用收点用vt表示，发点用表示，发点用vs表示，其他为中间点，其每表示，其他为中间点，其每条弧的权值称之为容量，在不超越每条弧的容量的前提条弧的权值称之为容量，在不超越每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大下，要求确定每条弧的流量，得出从发点到收点的最大流量。流

10、量。p在交通运输、物资供应、通讯系统和财政金融等实践任在交通运输、物资供应、通讯系统和财政金融等实践任务中，常会遇到这类最大流问题。务中，常会遇到这类最大流问题。 网络最大流问题最大流有关概念可行流与最大流 增广链的概念增广链的概念截集和截量截集和截量 截集和截量满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f = fij 称为可行流称为可行流 1) 0( , )ijijfci j（所有弧(3)stsjitvvvff发点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流的总流量量(2) mmimmjmvvffv所有中间点概念回想链：从发点到收点的一条道路弧的方向不

11、一定都同向称为链。链：从发点到收点的一条道路弧的方向不一定都同向称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：与链的方向一样的弧称为前向弧。前向弧：与链的方向一样的弧称为前向弧。后向弧：与链的方向相反的弧称为后向弧。后向弧：与链的方向相反的弧称为后向弧。增广链增广链: 设设 f 是一个可行流，假设存在一条从是一个可行流，假设存在一条从vs到到vt的链，满足：的链，满足：1.一切前向弧上一切前向弧上fij0那么该链称为增广链那么该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链844695(2)(3)(4)(6)寻觅网络最大流

12、的Ford-Fulkerson标号法 算法的步骤 算法的步骤算法举例算法举例算法举例算法举例算法举例算法举例算法举例(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的最大流及最大流量的最大流及最大流量无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以了解为一切弧都是前向弧，对一端无向图不存在后向弧，可以了解为一切弧都是前向弧，对一端vi已标号另一端已标号另一端vj未标号的边只需满足未标号的边只需满足 Cijfij0 那

13、么那么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,22v2,2(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,11(12 ,12)(9 ,7)(20 ,10)(8 ,8)(5 ,4)(8 ,3)

14、(7 ,7)(6 ,6)(14,8)(13 ,13)(9 ,3)(16 ,16)V=290,v1,10v3,5v4,5v5,5v4,1最小费用网络最大流问题 最小费用最大流问题 最小费用增广链 求最小费用流的根本思想 辅助赋权有向网络的构造方法 最小费用最大流算法步骤最小费用最大流算法运用举例 最小费用最大流算法运用举例最小费用最大流算法运用举例最小费用最大流算法运用举例最小费用最大流算法运用举例最小费用最大流算法运用举例最小费用最大流算法运用举例欧拉图欧拉链、欧拉圈与欧拉图p欧拉链欧拉链p 给定一个连通多重图给定一个连通多重图G，假设存在一条链，经过每边，假设存在一条链，经过每边一次且仅一次

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

16、奇点。个奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一邮递员担任某所谓中国邮递员问题，是指如下问题：某一邮递员担任某街区的邮件投递任务，每次都要从邮局出发走遍他担任的街区的邮件投递任务，每次都要从邮局出发走遍他担任的一切街道，再回到邮局，他应如何安排投递道路，使所走一切街道，再回到邮局，他应如何安排投递道路，使所走的总路程最短。的总路程最短。p中国邮递员问题的图论言语描画：给定一个连通图，在每中国邮递员问题的图论言语描画：给定一个连通图，在每边上边上ei上赋予一个非负的权上赋予一个非负的权w(ei) ,要求一个圈未必是要求一个圈未必是简单的，过每边至少一次，并使圈的总权最小。简单的，过每边至少一次，并使圈的总权最小。中国邮递员问题求解思索两种情形：思索两种情形：假设假设G是欧拉图，那么从邮局出发，每边恰好走一是欧拉图，那么从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；假设假设G不是欧拉图，那么某些边必然要反复走，我不是欧拉图，那么某些边必然要反复走，我们当然要求反复走过的边的总长最小。我们可以们当然要求反复走过的边的总长最小。