资源描述
,第,*,页,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学 课 件,图与网络分析,Network Analysis,1,第一节 图的基本概,念与模型,2,定义：,称,G=(N,E),是一个,图,，如果有,（,1,）,N,是非空有限集；,（,2,）,E,是,N,中元素对所组成的集合。,且，称,N,的元素为,顶点,，,E,的元素为,边,。,记号：图,G=(N,E),简记为,G,图,G,的顶点集,简记为,N(G),或,N,无向图的基本概念,3,G,的点集合,： （例如：图（1）中的,N=（1，2，3，4，5）,是一个无向图 的点的集合）,G,的边集合,：,E,=,e,ij,且,e,ij,=,n,i,n,j,为右,图,无序二元组,e,ij,的端点,：有,e,ij,=n,i,n,j,，,则称,n,i,和,n,j,为,e,ij,的端点，且称,e,ij,连接点,n,i,和,n,j,环,：两个端点重合为一点的边 （例如右图中的,e,11,）,孤立点,：不与任何边关联的点 （例如右图中的,n,5,）,3,4,5,1,2,4,度,V,3,V,1,V,2,V,4,V,5,各顶点度数为：,d(V,1,)=4 d(V,2,)=2,d(V,3,)=1 d(V,4,)=2 d(V,5,)=,？,无向图,G,有向图,D,V,1,V,2,V,3,V,4,各顶点度数为：,d(V,1,)=d,+,(V,1,)+ d,-,(V,1,)=3+0=3 d(V,2,)= d,+,(V,2,)+ d,-,(V,2,)=1+1=2,5,度的有关定理,定理,1,（握手定理）,设,G=,为任意图,(,无向的或者有向的,), V=v,1, v,2, , v,n,，边的条数,|E|=m,，,则,*推论,任何图,(,无向的或者有向的,),中，次数为奇数的顶点个数是偶数,。,定理,2,设,D=,为 有向图, V=v,1, v,2, , v,n,，边的条数,|E|=m,，则,6,续（1）,关联,：一条边的端点称为这条边的关联,邻接,：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的,有限图,：点和边都是有限集合的图,空图,：没有任何边的图,平凡图,：只有一个点的图,简单图,：既没有圈也没有两条边连接同一对点的图,7,完全图,：每一对点之间均有一条边相连的图,续（2）,偶图,(,二分图,):,若,N(G),能分解为,N,1,与,N,2,合于,N,1,N,2,=N(G), N1,N2=,且,N,i,自身的顶点互不相邻（,i=1,2,）则称,G,是偶图；记为,G=(N,1,N,2,E),8,完全偶图,:,不在同一顶点子集的任二顶点都相邻的简单偶图；,完全二分图,G,=(,S,T,E,)：,S,中的每个点与,T,中的每个点都相连的简单二分图,9,网络的基本概念,有向图,G,：,一个有序二员组(,N,A,)，,记为,G,=(,N,A,),G,的弧集合,：,A,=,a,ij,且,a,ij,=,n,i,n,j,为有序二元组 ，若,a,ij,=,n,i,n,j,，,则称,a,ij,从,n,i,连向,n,j,，,n,i,称为,a,ij,的尾，,n,j,为,a,ij,的头，,n,i,称为,n,j,的先辈，,n,j,称为,n,i,的后继,有向图,G,的基本图,：对于,G,的每条弧用一条边代替后得到的无向图,（有向）网络,G,：,对（有向）图,G,的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络。,10,关联矩阵,11,关联矩阵示例,右图的关联矩阵是,右图的关联矩阵是,1,3,4,5,2,1,3,4,2,12,邻接矩阵示例,图（7）的邻接矩阵是,图（8）的邻接矩阵是,1,3,4,5,2,1,3,4,2,13,子 图,14,定义,：,（通道、闭通道、开通道）,图,G,的顶点与边的交错序列,通道。,起点与终点重合的通道称为,闭通道,。,起点与终点不重合的通道称为,开通道,。,无向图的路,15,起点与终点不重合的迹称为,开迹,。,没有重复顶点的开通道称为,路,。,起点与终点重合的路称为,圈,。,注：迹是通道；路是开迹；圈是闭迹，反之不一定,定义,：,（迹、闭迹、开迹、路、圈）,没有重复边的通道称为,迹,。,起点与终点重合的迹称为,闭迹,。,16,连通性,点,i,和,j,点是连通的,：,G,中存在一条（,i，j）,路,G,是连通的,：,G,中任意两点都是连通的,连通分支,：,G,的极大连通子图,命题,:,设,G,有,p,个连通分支，则,G,的邻接矩,阵可以表示成分块矩阵,17,第二节,树图与图的最小部分（支撑）树,18,最小树,最小树及其性质,求最小树的,Kruskal,算法,(,避圈法,),算法步骤,算例,破圈法算法,算法步骤,算例,19,定义：,（树、生成树、最小生成树）,定理,1,：,设,T,是,(n,m),非平凡图，则下列命题等价：,（,1,）,T,是树；,（,2,）,T,无圈，,m=n-1,；,（,3,）,T,连通，,m=n-1,；,（,4,）,T,无圈，任加一边有唯一圈；,（,5,）,T,连通，任去一边不再连通；,（,6,）,T,的任二顶点恰有一条路连通；,无圈连通图称为,树,；图的生成子图若是树，则称为该图的,生成树；,树枝总和最小的生成树叫,最小生成树,20,注：,由以上定理知：,1,。,树是边数最少的连通图；,2,。,连通图的极大无圈生成子图是生成树；,3,。,连通图的极小连通生成子图是生成树。,21,Kruskal,算法步骤,22,算例,23,计算的迭代过程,24,例,1,：,已知任两城市间修建直通高速公路的费用，如何修建连通,n,个城市的高速公路网使总修建费用最少？,解：,1,。模拟图：,以,n,个城市为顶点，以任意两城市,u,v,间修建高速公路的费用为边,e=(u,v),的权，记为,w(u,v),或,w(e),，得赋权完全图,G=(N,E),。,2,。问题等价于,：求,G,的最小生成树，即边的权之和最小的生成树；,3,。求解：,思路,：用避圈法，可选择权相对最小的边作为“加边”，如此便得到最小生成树。,25,例,2,：,用,kruskal,法求下图的最小生成树。,26,破圈法：,任取一个圈，从圈中去掉一条权最大的边，在余下的图中重复此步骤。,练习：求下图的最小生成树,:,以上是一种算法，另外还可用,“破圈法”,:,27,第三节 最短路问题,28,29,30,31,32,33,综上，从,S,到,T,的最短输油管线路有两条，如下图所示,34,35,简化的图上操作方法,36,下求 到 的最短路：,1,）从 出发，向 走。首先，从 到 的距离为,0,，给,标号（,0,）。画第一个弧。（表明已 标号，或已走出 ）,从 出发，只有两条路可走 ，其距离为,2,）,37,可能最短路为, 给 划成粗线。,划第二个弧。,给 标号（,4,）。,38,表明走出 后走向 的最短路目前看是 ，最优距离,是,4,。,现已考察完毕第二个圈内的路，或者说，已完成,的标号。,39,3,）接着往下考察，有三条路可走：,可选择的最短路为, 给 划成粗线。,划第,3,个弧。,给 标号（,6,）。,40,4,）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。,划第,4,个弧。,给 标号（,8,）。,41,5,）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。,划第,5,个弧。,给 标号（,9,）。,42,6,）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。,划第,6,个弧。,给 标号（,13,）。,43,7,）接着往下考察，有四条路可走：,可选择的最短路为, 同时给 划成粗线。, 分别给 标号（,14,）。,44,最后，从 逆寻粗线到 ，得最短路：,长度为,15,。,45,最短路问题的两个应用,最短路问题在图论应用中处于很重要的地位，下面举两个实,际应用的例子。,设备更新问题,某工厂使用一台设备，每年年初工厂要作出决定：继续使,用，购买新的？如果继续使用旧的，要负维修费；若要购买,一套新的，要负购买费。试确定一个,5,年计划，使总支出最小,若已知设备在各年的购买费，及不同机器役龄时的残值与,维修费，如表,1,所示,.,46,项目,第,1,年,第,2,年,第,3,年,第,4,年,第,5,年,购买费,11,12,13,14,14,机器役龄,0-1,1-2,2-3,3-4,4-5,维修费,5,6,8,11,18,残值,4,3,2,1,0,表,1,47,解：把这个问题化为最短路问题。,用点 表示第,i,年初购进一台新设备，虚设一个点 ，表示第,5,年底。,边 表示第,i,年购进的设备一直使用到第,j,年初（即第,j-1,年底）。,48,边 上的数字表示第,i,年初购进设备，一直使用到第,j,年,初所需支付的购买费、维修的全部费用（可由表,8-2,计算得,到）。,这样设备更新问题就变为：求从 到 的最短路问题,.,49,给 划成彩线。,50,给 划成彩线。,给 划成彩线。,51,给 划成彩线。,52,给 划成彩线。,计算结果：最短路,53,最短路路长为,49,。,即：在第一年、第三年初各购买一台新设备为最优决策。,这时,5,年的总费用为,49,。,54,例,(,选址问题,),已知某地区的交通网络如图所示，,其中点代表居民小区，边代表公路，为小区间公路距离，问区,中心医院应建在哪个小区，可使离医院最远的小区居民就诊时,所走的路程最近？,解 求中心的问题。,解决方法：先求出 到,其它各点的最短路长,如,再求,55,即为所求。,比如求,给 划成彩线。,56,给 划成彩线。,给 标号,20,。,57,给 划成彩线。,给 标号,30,。,58,分别给 划成彩线。,分别给 标号,33,。,59,给 划成彩线。,给 标号,63,。,其它计算结果见下表：,60,小区号,0 30 50 63 93 45 60,93,30 0 20 33 63 15 30,63,50 20 0 20 50 25 40,50,63 33 20 0 30 18 33,63,93 63 50 30 0 48 63,93,45 15 25 18 48 0 15,48,60 30 40 33 63 15 0,63,表,2,由于 最小，所以医院应建在 ，此时离医院最,远的小区 距离为,48,。,61,三,. Floyd,（佛洛伊德）算法,这里介绍的,Floyd,算法（,1962,年）可直接求出网络中任意两点间的最短路。,令网络中的权矩阵为,其中,当,其他,算法基本步骤为：, 输入权矩阵,62,例,：,求右图中任意两点间的最短路, 计算,其中,例如：,63,中不带角标的元素表示从 到 的距离（直接有边），,带角标的元素表示借 为中间点时的最短路长。,64,中不带角标的元素表示从 到 的距离（直接有边），,带角标的元素表示借 为中间点时的最短路长。,在放开 的基础上，再放开,65,注意到：,在放开 点的基础上，再放开 考察最短路。,66,注意到：,67,说明所有点经过 并没有缩短路程。,68,只有一个新增元素,69,表示任意两点间的最短路长及其路径。,70,逐次逼近算法,注：,本算法可用于网络中有带负权的边，求某指定点,到网络中任意点的最短路。,算法思想：,如果,到,的最短路总沿着该路从,先到某一点,，然后再沿边,到达,，则,到达,的这条路必然也是,到达,到达,的最短路。,71,若令,表示从,到达,的最短路长，,表示从,到达,的最短路长，则必有,用迭代法解此方程：,首先，令,即是说，用,到达,的直接距离 做初始解 ，,并且，若他们之间无边，则记他们间 的最短路为,72,从第二步起用公式：,求,，当进行到第,t,步，若出现,则停止，,即为,到各点的最短路长 。,73,算例,求,到达,的最短路,74,第一次迭代,第二次迭代,75,第三次迭代,76,达到最优，回代得最短路：,77,例,求,v1,到,v8,的最短路,78,第一次迭代,第二次迭代,79,第三次迭代,80,继续下去。,81,达到最优，回代后得最短路为：,82,1,给标号 （,0,）。画弧。,简化的表上求解方法,83, 给 划成彩线。,划第二个弧。,给 标号（,-3,）。,84, 给 划成彩线。,划第三个弧。,给 标号（,1,）。,85, 给 划成彩线。,划第四个弧。,给 标号（,2,）。,86, 给 划成彩线。,划第五个弧。,给 再次标号（,0,）。,去掉 彩线。,87, 分别给 划成彩线。,划第六个弧。,分别给 标号（,6,）。,(4),由于,权为,3,，所以，将,的距离改为,3,88, 给 划成彩线。,划第七个弧。,给 标号（,10,）。,89, 给 划成彩线。,到达 已经无负权，路程不可能再减少。,给 标号（,9,）。,90,最短路径为：,距离：,10,。,91,第四节,中国邮路问题,92,例,1,：,18,世纪，在东普鲁士哥尼斯堡有座桥，如下图，一个散步者能否走遍七座桥，每座桥只走过一次，最后回到出发点？,B,C,D,93,定义：,（,Euler,开（闭）迹、,Euler,迹、可一笔画）,解：,1,。模拟图：以顶点表陆地，以边表桥，得,4,个顶点的模拟图。,2,。问题等价于：能否有一条闭迹包含模拟图的所有边，即：模拟图含有,Euler,闭迹吗？,3,。求解：假设图,G,含,Euler,闭迹。因为闭迹是连通的，所以图,G,也连通。又因为每个顶点既能到达也能离开，所以图,G,的每个顶点度都是偶数。,即：图,G,含,Euler,闭迹的必要条件：连通且没有奇度顶点。,所以，“七桥问题”是不可能的。,若有一条开（闭）迹含图,G,的所有顶点和边，则称其为,Euler,开（闭）迹,，,Euler,开（闭）迹统称,Euler,迹。可一笔画：,从起点到终点一笔画完。,94,定理,1,：,图,G,含,Euler,闭迹的充要条件是,G,连通且没有奇顶点。,定理,2,：,图,G,可一笔画的充要条件是,G,连通且奇顶点数是,0,或,2,。,邮路问题：,若一个邮递员在下图所示的街道上投递邮件，问如何投递才使得他走遍每一条街道，再返回邮局，且总路程最短？,1,1,1,1,1,1,1,1,95,问题分析：,据上面定理知，若街道图中没有奇点，则他就可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，如此他所走的路程即是最短路程。而对于有奇点的图，必须在某些街道上重复走一次或多次。（假定,N,1,为邮局）,这样，路线可有多种，例：,总权为,12,总权为,11,96,可见，按第一条路线，在边,上各重复走了一次，而按第二条路线，在边,上各重复走了一次。,因此，我们想到,，可在一个有奇点的图中，增加一些重复边，使得新图不含奇点，且要求重复边的总权最小。,注释,：,增加重复边使图无奇点的过程称为,可行方案,。,使总权最小的可行方案称为,最小方案,97,第一步（找初始可行方案）：,找到图中的奇点，把奇点两两相连，（因为，在任何图中奇点个数必为偶数）。,第二步（调整可行方案）：,调整时遵循两个原则：,（,a,）在最优方案中，图的每一条边上最多有一条重复边；（,b,）在最优方案中，图的每一个圈上重复边的总权不大于该圈总权的一半。（,若把图中某个圈上的重复边去掉，而给原来没有重复边的的边上加上重复边，图中仍没有奇点）,第三步（判断最优方案）：,检查条件（,a,），（,b,）是否满足，若是，则为最优。,得求解步骤：,98,例：,求解下面问题。,2,5,5,9,6,4,3,4,3,4,4,4,解：,奇点有：,连接,且连接,得：,2,5,5,9,6,4,3,4,3,4,4,4,99,因为圈,的总权为,24,，但重复边,的总权为,14,，大于该圈总权的一半，故需要调整，以,上的重复边代替,上的重复边，使重复边总长下降为,17,，,2,5,5,9,6,4,3,4,3,4,4,4,100,同理，调整圈,后，得,最优方案,：,2,5,5,9,6,4,3,4,3,4,4,4,注：此法称为奇偶点图上作业法，此法困难在于要检查所有圈，问题特复杂时应用它法。,101,第五节,网络最大流,102,103,可行流的流量：,104,3,。饱和、非饱和弧，,0,流、非,0,流弧，前向、后向弧,若,则为饱和弧，,若,则为非饱和弧,.,若,则为,0,流弧,，,若,则为非,0,流弧,.,寻求一条,st,的路，作为参照物。这条路经过的网络图的弧中,前向弧：凡是和此路方向相同的弧称为前向弧。,反向弧：凡是和此路方向相反的弧称为反向弧。,105,106,107,108,割集有,：,截量为,4,截量为,5,截量为,4,109,网络最大流算法的理论依据,只有找不到增广链时，网络才能达到最大流,这是因为：有增广链时，能找到一个,若令,得到了，一个流量更大的可行流,110,111,最小割与最大流的关系,最小割最大流定理,割集有,：,截量为,4,截量为,5,截量为,4,112,算例,求下图的最大流,113,解,：,（,1,）先给,标号（,0,，,）；,（,2,）从,出发的弧,（,3,）从,到,的弧,114,（,4,）从,出发的弧,（,5,）从,到,的弧,115,（,6,）从,到,的弧,有了标号，也得到了一条增广链如图,116,调整后得到下图,继续标号如下：,117,（,1,）给,标号（,0,，,）；,（,2,）从,出发的弧,下面无法进行，所以达到最大流。此时的最大流量为,所以,为最小割。,118,最大流问题的应用,1.,最大匹配问题,二部图（也叫二分图）,图,G= (V, E),若,V=XY,且,XY=,，使得,E,中每一条边,的两个端点必有一个属于,X,，另一个属于,Y,，则称,G,为二,部图。记,G=,（,X,，,Y,，,E,），或,G=,（,X,，,E,，,Y,）。,119,匹配：,对给定的二部图,G =,（,X,，,Y,，,E,），,若有,M,包含于,E,，且,M,中任意两条边都没有公共端点，则称,M,为,G,的一个匹配,（也称对集）。,既满足：一个人最多做一件工作，每件工作最多由一人来,做。即为工作集与工人集之间的一个匹配。,120,最大匹配问题：,Q,表示,G,中所有的匹配集，即,Q,=,M | M,为,G,的匹配集,|M|,表示,M,的边数，若存在,M,0,使对任意的,M,Q,，有,则称,M,0,是,G,的最大匹配。,注：,G,中最大匹配方案可能不唯一。,饱和点：,M,中任意边的端点称为（关于,M,的）饱和点（即已经有匹配的顶点），,G,中其他顶点称为非饱和点。,121,例：多端网络问题,设有,5,位待业者，,5,项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。,其中,表示工人。,表示工作。,122,二部图中最大匹配问题，可以转化为最大流问题求解。在,二部图中增加两个新点 分别作为发点，收点。并用,有向边把它们与原二部图中顶点相连，令全部边上的容量,均为,1,。当网络流达到最大时，如果 上的流量为,1,，,就让 作 工作，此即为最大匹配方案。,123,第一次标号。,调整,124,第二次标号。,再调整。,125,第三次标号。,126,调整。,127,第四次标号。,128,调整,129,第五次标号。,130,标号过程已无法再继续。流量为,1,的画彩线。,131,工人,分别作,故最多安排四个人工作。,132,应用,2,：货物运输问题,例：现有,5,批货物，每批只需一条船装,运，要由 ， 所在地域运往 ， ， 地域。至于货物,从 ， 运向 ， ， 三点何处都一样，每批货物出,发日期如表,1,，,船,航行所需天数如表,2,。船只空载和,重载时航行时间相同。要求制定一个计划，在半个月内用,最少的船只把,5,批货物运过去。,地点,5,10,/,/,12,1,，,8,地点,2,3,2,1,1,2,表,1,（出发日期）,表,2,（航行天数）,133,解：设 ， 分别表示每项运输任务的出发日期及,完成日期（,i=1,，,2,，,3,，,4,，,5,）则由表,1,和表,2,知：,任务,路线,5,7,10,13,12,13,1,3,8,10,134,任务,路线,5,7,10,13,12,13,1,3,8,10,要想用较少的船只在,1,15,天内完成任务，关键是自上一任,务到达的时间加上返回的时间能否赶上下一个任务出发的,时间。若能，则一只船就能完成两批货物的运输任务。,以下试运行：,135,任务,路线,5,7,10,13,12,13,1,3,8,10,5,号,7,号,8,号回,10,号,地点,2,3,2,1,1,2,表,2,（航行天数）,8,号,12,号回,13,号,14,号回,136,任务,路线,5,7,10,13,12,13,1,3,8,10,10,号,3,号,地点,2,3,2,1,1,2,表,2,（航行天数）,1,号,13,号,5,号回,共两只船在,13,号以前就把,5,批货物全部运了出去。,是否最优？一只船可行否？如何解决？,137,作一个二部图，点集,X,和,Y,都表示这,5,项任务，两,点间有连线的条件是第,i,件任务完成后可赶上作第,j,件任务。,有连线即有匹配，连线越多（匹配数越大）一只船重复使,用次数多，使用船只数就越少。最大的匹配就是用最少的,船。,任务,路线,5,7,10,13,12,13,1,3,8,10,138,任务,路线,5,7,10,13,12,13,1,3,8,10,地点,2,3,2,1,1,2,表,8-6,（航行天数）,此时的,m1-5,n1-5,分别表示任务,1,5,。,139,此表示共两只船可完成任务：,：,：,140,例：某河流中有几个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图，在一次敌对的军事行动中，问至少应炸断几座桥，才能完全切断两岸的交通。,141,142,例,：（,匹配问题）有三根相同的轴（编号为,1,，,2,，,3,），又有三个相同的齿轮（编号为,4,，,5,，,6,），由于精度不高，不能做到任意匹配。据图纸工艺要求，已知轴,1,能和齿轮,4,，,5,配合，轴,2,能和齿轮,5,，,6,配合，轴,3,能和齿轮,4,，,5,配合。要求合理选择装配方案，以得到轴与齿轮的最大匹配数。,143,144,最小费用流,145,在一个关于流的网络中，人们不仅需要流达到一定的数量，（甚至达到最大，即最大流）而且每一个流量要有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，可能走的路线不一样，总的费用不一样。从而在限定网络流的基础上，让流沿那些边走，能使总的费用最小（这里的最小费用问题又看成最短路问题）。,特别的，当最大流不惟一时，在所有最大流中求一个流,f,使,总费用最低,。,146,问 题,147,对偶算法的算法思想,从零流 开始，以费用作为边的长度，构造出一个长度网络，对此长度网络，用求最短路的方法，求出费用最小的可增广链，在找到的增广链上调整流量，使其流量逐步达到要求的数量。,148,相关定义,定义,：（,链的费用）,已知网络,f,是,G,上的一个可行流，,可增广链，,称为链,的费用。,定义,：（,流的总费用）,149,相关定理,定理：若,f,是流量为,的最小费用流，,则,得到新可行流,一定是,流量为,的可行流中的最小费用流。,的一条最小费用可增广链，,150,定义,：（,长度网络）对网络,有可行流,f,，保持原网络各点，按以下规则定义网络：,这样得到的一个网络称为长度网络。记为,L(f),151,对偶算法的步骤,（,1,）取,0,流为初始可行流,（,2,）若有,流量为,构造长度网络,（,3,）在长度网络,中求从,若不存在最短路，则,已为最大流，不存在流量,为,v,的流，停止；否则转（,4,）；,（,4,）在,G,中与这条最短路相应的可增广链上，令,152,此时,的流量为,若,则，停止，否则令,代替,返回（,2,）。,153,算 例,在下图所示网络图上，求流量为,v=10,的最小费用流，图中所示为,154,解：从,开始，作,如下,用,Dijkstra,算法求得,网络中的最短路为,155,在网络,G,中相应的增广链,上用最大流算法进行流的调整,156,此时，有,依次作,157,由前面的逐次逼近算法的计算结果得最短路为,在网络,G,中相应的增广链,上用最大流算法进行流的调整,158,此时，有,又作,159,由前面的逐次逼近算法得最短路为,160,上用最大流算法进行流的调整,在网络,G,中相应的增广链,161,此时，有,162,
展开阅读全文