第6章图与网络分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 图与网络分析,图的基本概念与模型,树图和图的最小部分树,最短路问题,网络的最大流,最小费用流,1.,图的基本概念与模型,运筹学中研究的图用来表明一些研究,对象,和这些对象之间的相互,关系,。,用点表示研究对象，用边表示这些对象之间的联系，则图,G,可以定义为,点,和,边,的集合，记作,G=V,，,E,如果给图中的点和边赋以具体的含义和权数，如距离、费用等，称为,网络图,。,端点、关联边、相邻,环、多重边、简单图,次、奇点、偶点、孤立点,链、圈、路、回路、连通图,完全图、偶图,子图、部分图,【,例,】,有甲、乙、丙、丁、戊、己六名运动员报名参加,A,、,B,、,C,、,D,、,E,、,F,六个项目的比赛。如下表所示，打的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,甲,乙,丙,丁,戊,己,A,C,B,E,D,F,2.,树图和图的最小部分树,树图是无圈的连通图。,性质,1,：任何树图中必存在次为,1,的点；,性质,2,：具体,n,个顶点的树图的边数恰好为（,n-1,）条；,性质,3,：任何具有,n,个点、（,n-1,）条边的连通图是树图。,2.,树图和图的最小部分树,图的最小部分树,如果,G,1,是,G,2,的部分树，又是树图，则称,G,1,是,G,2,的部分树（或支撑树）。,树图的各条边称为树枝，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。,定理,1,：图中任一个点,i,，若,j,是与,i,相邻点中距离最近的，则边,i,，,j,一定必含在该图的最小部分树内。,推论：把图的所有点分为,V,和,V,两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,D,E,避圈法,【,例,】,如下图所示，,S,、,A,、,B,、,C,、,D,、,E,、,T,代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,D,E,破圈法,【,例,】,如下图所示，,S,、,A,、,B,、,C,、,D,、,E,、,T,代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,3.,最短路问题,最短路问题一般来说就是,从给定的网络图中找出任意两点之间距离最短的一条路,。这里的距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。,求解最短路问题有两种算法：,求从某一点至其它各点之间最短距离的,狄克斯屈拉,（,Dijkstra,）算法；,求网络图上任意两点之间最短距离的,矩阵,算法；,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L,11,=0,L,1p,=minL,11,+d,12,L,11,+d,13,=min0+5,0+2=2=L,13,L,1p,=minL,11,+d,12,L,13,+d,34,L,13,+d,36,=min0+5,2+7,2+4=5=L,12,L,1p,=minL,12,+d,25,L,12,+d,24,L,13,+d,34,L,13,+d,36,=,=min5+7,5+2,2+7,2+4=6=L,16,2,5,6,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L,1p,=minL,12,+d,25,L,12,+d,24,L,13,+d,34,L,16,+d,64,L,16,+d,65,L,16,+d,67,=min5+7,5+2,2+7,6+2,6+1,6+6=7=L,14,=L,15,L,1p,=minL,15,+d,57,L,16,+d,67,=min7+3,6+6=10,=L,17,2,5,6,7,7,10,【,练习,】,4,6,5,7,1,5,5,2,4,1,6,8,0,4,5,5,9,10,16,矩阵算法,5,7,2,2,1,2,6,6,4,3,7,构造一个新矩阵,D,（,1,）,该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵,D,（,1,）,中每个元素的计算方式为：,一般有矩阵,D,（,k,）,给出了网络中任意两点之间直接到达，经过一个、两个、,、到（,2,k,-1,）个中间点时比较得到的最短距离。矩阵,D,（,k,）,中每个元素的计算方式为：,【,例,】,某人购买一台摩托车，准备在今后,4,年内使用。他可在第一年初购买一台新车，连续使用,4,年，也可于任何一年末换一台新车。已知各年初的新车购置价如下表,1,。不同役龄车的年使用维护费及年末处理价如下表,2,。要求确定该人使用摩托车的最优更新策略，使,4,年内用于购买、更新及使用维护的总费用为最省。单位：万元。,第一年,第二年,第三年,第四年,年初的购置价,2.5,2.6,2.8,3.1,摩托车役龄,01,年,12,年,23,年,34,年,年使用维护费,0.3,0.5,0.8,1.2,该役龄年末处理费,2.0,1.6,1.3,1.1,第一年,第二年,第三年,第四年,年初的购置价,2.5,2.6,2.8,3.1,摩托车役龄,01,年,12,年,23,年,34,年,年使用维护费,0.3,0.5,0.8,1.2,该役龄年末处理费,2.0,1.6,1.3,1.1,0.8,0.9,1.1,1.4,1.7,1.8,2,2.8,2.9,4.2,0,0.8,1.7,2.6,3.7,一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程为最短。因为这个问题由中国数学工作者提出，故称为,中国邮路问题,。,欧拉回路,的定义是：连通图,G,中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。,【,例,】,设某邮递员负责投递的街道如图所示，要求找出该邮递员的最短投递路线。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,连通图,G,是欧拉图的充分必要条件是图中的点全为,偶点,。,（,1,）每条边上最多重复一次；,（,2,）在图,G,的每个回路上，有重复边的长度不超过回路总长的一半。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,4.,网络最大流,网络最大流的有关概念,有向图与容量网络,有向图上的连线是有规定指向的，称作,弧,；,所谓容量网络是指对网络上的每条弧都给出一个最大的通过能力，称为该,弧的容量,，记为,c(v,i,v,j,),或简写,c,ij,；,在容量网络中通常规定一个,发点,（记为,s,）和一个,收点,（记为,t,），网络中既非发点又非收点的其它点称为中间点；,网络最大流,是指网络中从发点到收点之间允许通过的最大流量。,4.,网络最大流,流与可行流,所谓,流,是指加在网络各条弧上的一组负载量，记作,f(v,i,v,j,),或简写为,f,ij,；,若网络上所有的,f,ij,=0,，这个流称为,零流,；,在容量网络上满足以下条件的一组流称为可行流：,容量限制条件，对所有弧有,中间点平衡条件,4.,网络最大流,割和流量,割是指将容量网络中的发点和收点分割开，并使,st,的流中断的一组弧的集合。,割的容量是组成它的集合中的各弧的容量之和。,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),V,V,割,容量,4.,网络最大流,最大流最小割定理,如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为,st,的弧（称为,前向弧,，记作,+,），存在,f0,，这样的链称为,增广链,。,4.,网络最大流,最大流最小割定理,当增广链存在时，找出,再令,定理：,在网络中,st,的最大流量等于它的最小割集的容量,。,4.,网络最大流,Ford-Fulkerson,标号算法,首先给发点,s,标号 。括弧中的第一个数字是使这个点得到标号的前一个点的代号；括弧中的第二个数字表示从上一个标号到这个标号点的流量的最大允许调整值。,列出与已标号点相邻的所有未标号点：,考虑从已标号点,i,出发的弧（,i,，,j,）：,j,点不标号,j,点标号,列出与已标号点相邻的所有未标号点：,考虑所有指向已标号点,i,的弧（,h,，,i,）：,如果某未标号点,k,有两个以上相邻的标号点，为减少迭代次数，可按,I,、,II,中所述规则分别计算出 的值，并取其中最大的一个标记。,重复第,2,步，可能出现两种结局：,标号过程中断，,t,得不到标号，说明网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为,V,未标号点集合为,V,，（,V,，,V,）为网络的最小割；,t,点得到标号，反向追踪找出增广链；,h,点不标号,h,点标号,修改流量，设图中原有可行流为,f,，按一下方式获得新的可行流,f,：,抹掉图中所有标号，重复第,1,到第,4,步，直至图中找不到任何增广链，即出现第,3,步的结局,I,为止，这时网络图中的流量即为最大流。,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),7(,6,),5(,3,),9(,5,),6(,0,),10(,9,),最小割,最大流：,14,5(5),6(4),3(3),5(4),2(0),3(3),3(2),4(4),2(2),2(0),8(6),6(6),5(5),6(,5,),3(3),5(,5,),2(0),3(,2,),3(,3,),4(4),2(,1,),2(0),8(,7,),6(6),最小割,最大流：,13,D,B,C,E,A,F,1,2,3,4,5,6,7,8,9,10,11,12,13,【,例,】,某河流中有,4,个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图所示，在一次敌对的军事行动中，问至少应炸断哪几座桥梁，才能完全切断两岸的交通联系？,D,B,C,E,A,F,1,2,3,4,5,6,7,8,9,10,11,12,13,A,B,C,D,E,F,2,2,1,2,1,1,1,1,3,A,B,C,D,E,F,2(1),2,1(,1,),2(1),1,1,1,1(1),3(,1,),A,B,C,D,E,F,2(1),2,1(1),2(1),1,1,1,1(1),3(1),A,B,C,D,E,F,2(,2,),2,1(1),2(,2,),1,1,1(,1,),1(1),3(,2,),最小割：,(D,F),(D,E),(A,E),D,B,C,E,A,F,1,2,3,4,5,6,7,8,9,10,11,12,13,5.,最小费用流,最小费用流问题,对于容量网络，除考虑各条弧上的流量、容量外，还需考虑弧上通过单位流量时的费用（,b,ij,），保证最终给出的流量或最大流也是费用最少的。,关键点：确定“,最小费用增广链,”。,(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),【,例,】,各弧旁数字为,(,c,ij,b,ij,),，试求图中从,st,的最小费用最大流。,从原容量网络的零流,f,0,开始；,对原容量网络的可行流,f,k,构造,加权网络,W(f,k,):,对,0,f,ij,c,ij,的弧,(i,j),，在加权网络的,i,点和,j,点之间分别绘制弧,(i,j),和,(j,i),，其权数分别为,b,ij,和,-,b,ij,；,对,f,ij,=,c,ij,的弧，在加权网络的,i,点和,j,点之间绘制弧,(j,i),，其权数为,-,b,ij,；,对,f,ij,=0,的弧，在加权网络的,i,点和,j,点之间绘制弧,(i,j),，其权数为,b,ij,。,确定最小费用增广链等价于求解加权网络,st,之间的最短路。找出增广链之后调整原容量网络的流量；,重复,2,、,3,步骤，直到,st,之间找不出最短路为止，此时求得原容量网络的最小费用最大流。,5.,最小费用流,(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),8,7,5,9,9,2,4,0,7,8,10,14,5(,3,),8(0),2(0),4(0),10(0),3(,3,),8(,3,),(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),5(,3,),8(0),2(0),4(0),10(0),3(,3,),8(,3,),8,7,5,9,9,4,-8,-2,-4,8,7,5,9,9,4,-8,-2,-4,5(,3,),8(0),2(0),4(0),10(0),3(,3,),8(,3,),5(,5,),8(0),2(0),4(,2,),10(0),3(3),8(3),8,7,5,9,9,4,-8,-2,-4,(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),5(,5,),8(0),2(0),4(,2,),10(0),3(3),8(3),7,5,9,9,4,-8,-2,-4,-9,7,5,9,9,4,-8,-2,-4,-9,7,5,9,9,4,-8,-2,-4,-9,5(,5,),8(0),2(0),4(,2,),10(0),3(3),8(3),5(5),8(,5,),2(0),4(2),10(,5,),3(3),8(,8,),(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),5(5),8(,5,),2(0),4(2),10(,5,),3(3),8(,8,),7,5,9,9,-8,-2,-4,-9,-7,-9,7,5,9,9,-8,-2,-4,-9,-7,-9,7,5,9,9,-8,-2,-4,-9,-7,-9,5(5),8(,5,),2(0),4(2),10(,5,),3(3),8(,8,),5(5),8(,7,),2(,2,),4(,4,),10(5),3(3),8(8),(5,8),(8,7),(2,5),(4,9),(10,9),(3,2),(8,4),5(5),8(,7,),2(,2,),4(,4,),10(5),3(3),8(8),7,-5,9,-8,-2,-4,-9,-7,-9,7,-5,9,-8,-2,-4,-9,-7,-9,5(5),8(,7,),2(,2,),4(,4,),10(5),3(3),8(8),