图与网络分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学Operations Research,Mob.:,1,图与网络分析,在现实生活和生产活动中，许多问题都可以用网络模型来描写。如：在现有交通网络中，如何使调运的物资数量多且费用最小等。,网络模型就是一种应用图论的理论与方法解决具有网络性质的管理决策问题的数学模型。,网络模型具有图形直观，方法简便，容易掌握的特点，广泛地应用在各个领域，尤其是经济活动中许多管理决策的优化问题。,2,图与网络的基本概念,3,图及其分类,图,是点与线的集合。一个图由一些点及一些点之间的联线(不带箭头或带箭头)所,组成。,为了区别起见。把两点之间的带箭头的联线称为,边,，带箭头的联线称为,弧,。,用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。,4,无向图,由点和边组成的图称为,无向图,。,5,无向图,6,环、多重边、简单图、多重图,7,点的次,8,链、圈、连通图,9,子图,10,子图,v,1,11,有向图,由点和弧组成的图称为,有向图,。,12,环、多重弧、简单有向图,13,点的出次和入次 、路,14,网络的概念,15,图的矩阵表示 ：关联矩阵,16,图的矩阵表示 ：邻接矩阵,17,图的矩阵表示 ：权矩阵,18,树与最小树问题,19,树的概念和性质,v,1,v,2,v,3,v,4,v,5,v,6,4,3,2,1,7,20,树的概念和性质,21,支撑树,22,用破圈法与避圈法求支撑树,23,最小树,破圈法,：任取一圈，去掉圈中最长边，直到无圈。,24,最小树,5,v,1,v,2,v,3,v,4,v,5,v,6,8,4,3,7,5,2,6,1,8,【例8.1】用破圈法求下图的最小树。,最小树长为,C(T)=4+3+5+2+1=15。,当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,25,避圈法,：取图,G,的,n,个孤立点,v,1,，,v,2,，,v,n,作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v,1,v,2,v,3,v,4,v,5,v,6,4,3,5,2,1,在上图中，如果添加边,v,1,v,2,就形成圈,v,1,v,2,v,4,，这时就应避开添加边,v,1,v,2,，添加下一条最短边,v,3,v,6,。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等,5,v,1,v,3,v,5,1,5,v,2,v,4,v,6,8,4,3,7,5,2,6,8,Min C(T)=15,26,最小树的寻找方法：矩阵法,27,矩阵法举例,28,矩阵法,29,矩阵法举例,30,矩阵法举例,31,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法：,一是求从某一点至其它各点之间最短离的,狄克斯屈拉(Dijkstra)算法,另一种是针对网络中有负权的,逐次逼近法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,最短路问题,32,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,【例8.3】下图中的权,c,ij,表示,v,i,到,v,j,的距离（费用、时间），从,v,1,修一条公路或架设一条高压线到,v,7,，如何选择一条路线使距离最短，建立该问题的网络数学模型。,33,【解】 设,x,ij,为选择弧(,i,，,j,)的状态变量，选择弧(,i,，,j,)时,x,ij,1，不选择弧(,i,，,j,)时,x,ij,0，得到最短路问题的网络模型：,34,Dijkstra标号法原理,35,Dijkstra标号法原理,36,Dijkstra算法的具体步骤,37,Dijkstra算法的具体步骤,38,6,10,12,3,2,14,6,7,5,8,11,16,5,9,(6,v1),(12,v1),(16,v3),(18,v3),(29,v5),【例8.3】用Dijkstra算法求下图所示,v,1,到,v,7,的最短路及最短路长,v,1,到,v,7,的最短路为：,p,17,=,v,1,v,2,v,3,v,5,v,7,，最短路长为,L,17,=29,39,Dijkstra,算法举例,40,Dijkstra算法举例,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,41,逐次逼近法,42,逐次逼近法,43,逐次逼近法举例,44,逐次逼近法举例,45,逐次逼近法举例,46,逐次逼近法举例,47,最短链问题,48,最短链问题,49,最短链问题举例,50,最短链问题举例,51,最短链问题举例,52,最短链问题举例,53,最短链问题举例,54,最短链问题举例,55,网络最大流问题,所谓,最大流量问题,就是：给一个带收发点的网络（一般收点用,v,t,表示，发点用,v,s,表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。,在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。,56,网络最大流问题,57,最大流有关概念,58,可行流与最大流,59,增广链的概念,60,增广链的概念,61,截集和截量,62,截集和截量,63,截集和截量,64,满足下例3个条件的流,f,ij,的集合,f,=,f,ij,称为,可行流,发点,v,s,流出的总流量等于流入收点,v,t,的总流量,概念回顾,65,链：,从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：,与链的方向相同的弧称为前向弧。,后向弧：,与链的方向相反的弧称为后向弧。,增广链:,设,f,是一个可行流，如果存在一条从,v,s,到,v,t,的链，满足：,1.所有前向弧上,f,i,j,0,则该链称为增广链,前向弧,后向弧,容量,流量,这是一条增广链,8,4,4,6,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】求下图发点,v,1,到收点,v,7,的最大流及最大流量,77,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端,v,i,已标号另一端,v,j,未标号的边只要满足,C,ij,f,ij,0 则,v,j,就可标号（,C,ij,f,ij,）,【例8.8】求下图,v,1,到则,v,7,标的最大流,(,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,2,v4,2,v5,2,v6,2,v2,2,78,(,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,3,v4,3,v5,3,v6,1,79,(,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=29,0,v1,10,v3,5,v4,5,v5,5,v4,1,80,最小费用网络最大流问题,81,最小费用最大流问题,82,最小费用增广链,83,求最小费用流的基本思想,84,辅助赋权有向网络的构造方法,85,最小费用最大流算法步骤,86,最小费用最大流算法应用举例,87,最小费用最大流算法应用举例,88,最小费用最大流算法应用举例,89,最小费用最大流算法应用举例,90,最小费用最大流算法应用举例,91,最小费用最大流算法应用举例,92,最小费用最大流算法应用举例,93,欧拉图,94,欧拉链、欧拉圈与欧拉图,欧拉链,给定一个连通多重图G，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。,欧拉圈,若存在一个简单圈，过每边一次，称这个圈为欧拉圈。,欧拉图,一个具有欧拉圈的图，称为欧拉图。 。,上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。,95,定理与推论,定理1,连通多重图G 是欧拉图的充要条件是图中的点全为偶点。,定理2,连通多重图G有欧拉链，当且仅当G中恰有两个奇点。,上述两个定理可用来识别一个图能否一笔画出。,96,中国邮递员问题,中国邮递员问题由我国学者管梅谷在1962年首先提出。,所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。,中国邮递员问题的图论语言描述：给定一个连通图，在每边上,e,i,上赋予一个非负的权,w,(,e,i,) ,要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。,97,中国邮递员问题求解,考虑两种情形：,如果,G,是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；,如果,G,不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以用“奇偶点图上作业法”解决这一问题。,98,“奇偶点图上作业法”相关定理,99,奇偶点图上作业法,100,奇偶点图上作业法举例,101,奇偶点图上作业法举例,102,奇偶点图上作业法举例,103,奇偶点图上作业法举例,104,奇偶点图上作业法举例,105,【例】求解下图的中国邮路问题,3,5,v,1,v,2,v,4,v,5,v,6,v,7,4,7,5,2,6,1,8,v,3,4,1,奇偶点图上作业法举例,106,5,v,1,v,2,v,4,v,5,v,6,v,7,4,3,7,5,2,6,1,8,v,3,4,1,4,1,【解】最优解如下图,1,4,上图为最短欧拉回路，重复经过了1，2和6，7两条边,107,