数模培训_图论模型2012

,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,图 论 模 型,数学建模培训,1,图论模型,图论基本概念,最短路径算法,最小生成树算法,遍历性问题,5.,网络流问题,2,1,引言,图论起源于,18,世纪。第一篇图论论文是瑞士数学家欧拉于,1736,年发表的,“,哥尼斯堡的七座桥,”,。,哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是,要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。,3,4,当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。,欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有,四个,“,点,”,，七条,“,线,”,的,“,图,”,。问题成为,从任一点出发一笔画出七条线再回到起点,。欧拉考察了一般一笔画的结构特点，给出了,一笔画的一个判定法则,：,这个图是连通的，且每个点都与偶数线相关联，,将这个判定法则应用于七桥问题，得到了,“,不可能走通,”,的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。,5,我们首先通过一些例子来了解网络优化问题。,例,1,最短路问题,（,SPP,shortest path problem,）,一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。,例,2,公路连接问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,6,例,3,指派问题,（,assignment problem,） 一家公司经理准备安排名员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。 如何分配工作方案可以使总回报最大？,7,上述问题有两个共同的特点：,一是,它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（,optimization,）问题；,二是,它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（,network,）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （,netwok optimization,）问题。,8,图的定义,图论中的,“,图,”,并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统,.,定义,1,一个有序二元组,(,V,E,),称为一个,图,记为,G,= (,V,E,),其中,V,称为,G,的顶点集,V,其元素称为,顶点,或,结点,简称,点,;,E,称为,G,的边集,其元素称为,边,它联结,V,中的两个点,如果这两个点是无序的,则称该边为,无向边,否则,称为,有向边,.,如果,V,= ,v,1,v,2, ,v,n,是有限非空点集,则称,G,为,有限图,或,n,阶图,.,2024/9/21,9,如果,E,的每一条边都是无向边,则称,G,为,无向图,(,如图,1),;,如果,E,的每一条边都是有向边,则称,G,为,有向图,(,如图,2),;,否则,称,G,为,混合图,.,图,1,图,2,并且常记,V,= ,v,1,v,2, ,v,n,|,V,|,=,n,;,E,= ,e,1,e,2, ,e,m,(,e,k,=,v,i,v,j,) ,|,E,|,=,m,.,称点,v,i,v,j,为边,v,i,v,j,的,端点,.,在有向图中,称点,v,i,v,j,分别为边,v,i,v,j,的,始点,和,终点,.,该图称为,(n,m),图,2024/9/21,10,对于一个图,G,= (,V,E,),人们常用图形来表示它,称其为,图解,.,凡是有向边,在图解上都用箭头标明其方向,.,例如,设,V,= ,v,1,v,2,v,3,v,4,E,= ,v,1,v,2,v,1,v,3,v,1,v,4,v,2,v,3,v,2,v,4,v,3,v,4,则,G,= (,V,E,),是一个有,4,个顶点和,6,条边的图,G,的图解如下图所示,.,2024/9/21,11,一个图会有许多外形不同的图解,下面两个图表示同一个图,G,= (,V,E,),的图解,.,其中,V,= ,v,1,v,2,v,3,v,4,E,= ,v,1,v,2,v,1,v,3,v,1,v,4,v,2,v,3,v,2,v,4,v,3,v,4,.,这两个图互为,同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图,.,2024/9/21,12,有边联结的两个点称为,相邻的点,有一个公共端点的边称为,相邻边,.,边和它的端点称为,互相关联,.,常用,d,(,v,),表示图,G,中与顶点,v,关联的边的数目,d,(,v,),称为顶点,v,的,度数,.,对于有向图,还有,出度,和,入度,之分,.,d,(,v,1,)=,d,(,v,3,)=,d,(,v,4,)=4,d,(,v,2,)=2.,握手定理：,2024/9/21,13,定义,2,若将图,G,的每一条边,e,都对应一个实数,F,(,e,),则称,F,(,e,),为该边的,权,并称图,G,为,赋权图,(,网络,),记为,G,= (,V,E,F,),.,定义,3,任意两点均有通路的图称为,连通图,.,定义,4,连通而无圈的图称为,树,常用,T,表示树,.,2024/9/21,14,图的矩阵表示,邻接矩阵 邻接矩阵表示了点与点之间的邻接关系,.,一个,n,阶图,G,的邻接矩阵,A,= (,a,ij,),n,n,其中,2024/9/21,15,无向图,G,的邻接矩阵,A,是一个对称矩阵,.,权矩阵,一个,n,阶赋权图,G,= (,V,E,F,),的权矩阵,A,= (,a,ij,),n,n,其中,16,无向图,G,的权矩阵,A,是一个对称矩阵,.,2024/9/21,17,关联矩阵（略）,一个有,m,条边的,n,阶有向图,G,的关联矩阵,A,= (,a,ij,),n,m,其中,若,v,i,是,e,j,的始点,;,若,v,i,是,e,j,的终点,;,若,v,i,与,e,j,不关联,.,2024/9/21,18,一个有,m,条边的,n,阶无向图,G,的关联矩阵,A,= (,a,ij,),n,m,其中,若,v,i,与,e,j,关联,;,若,v,i,与,e,j,不关联,.,2024/9/21,19,2,、最短路径,算法,定义,1,设,P,(,u,v,),是赋权图,G,= (,V,E,F,),中从点,u,到,v,的路径,用,E,(,P,),表示路径,P,(,u,v,),中全部边的集合,记,则称,F,(,P,),为路径,P,(,u,v,),的,权,或,长度,(,距离,),.,定义,2,若,P,0,(,u,v,),是,G,中连接,u,v,的路径,且对任意在,G,中连接,u,v,的路径,P,(,u,v,),都有,F,(,P,0,),F,(,P,),则称,P,0,(,u,v,),是,G,中连接,u,v,的,最短路,.,2024/9/21,20,重要性质：,若,v,0,v,1,v,m,是,图,G,中从,v,0,到,v,m,的最短路,则,1,k,m,v,0,v,1,v,k,必为,G,中从,v,0,到,v,k,的最短路,.,即：最短路是一条路，且最短路的任一段也是最短路,.,求非负赋权图,G,中某一点到其它各点最短路，一般用,Dijkstra,标号算法；求非负赋权图上任意两点间的最短路，一般用,Floyd,算法,.,这两种算法均适用于有向非负赋权图,.,下面分别介绍两种算法的基本过程,.,2024/9/21,21,Dijkstra,算法,求最短路已有成熟的算法：迪克斯特拉（,Dijkstra,）算法，其基本思想是按距,u,0,从近到远为顺序，依次求得,u,0,到的,G,各顶点的最短路和距离，直至所有顶点，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。,2024/9/21,22,Dijkstra,算法,用,d,ij,表示两相邻点,i,与,j,的距离。若,i,与,j,不相邻，令,d,ij,=,，显然,d,ii,=0.,用,L,si,表示从,s,点到,i,点的最短距离。现要求从,s,点到某一点,t,的最短路，用,Dijkstra,算法步骤如下：,2024/9/21,23,1,、从,s,点出发，因,L,ss,=0,，将此值标注在,s,旁的小方框内，表示,s,已标号。,2,、从,s,点出发，找出与,s,相邻的点中距离最小的一个，设为,r,，将,L,sr,=L,ss,+d,sr,的值标注在,r,旁，表明,r,已标号。,3,、从已标号的点出发，找出与这些点相邻的所有未标号点,p,。若有,L,sp,=minL,ss,+d,sp,;L,sr,+d,rp,则对,p,点标号，并将,L,sp,的值标注在,p,点旁的小方框内。,4,、重复第,3,步，一直到,t,点得到标号为止。,24,例 求下图,v1,点到,v7,点的最短路,.,25,Floyd,算法,（求任意两点的最短路径）,设,A,= (,a,ij,),n,n,为赋权图,G,= (,V,E,F,),的权矩阵,d,ij,表示从,v,i,到,v,j,点的距离,r,ij,表示从,v,i,到,v,j,点的最短路中前一个点的编号,.,赋初值,.,对所有,i,j,d,ij,=,a,ij,r,ij,=,j,.,k,= 1.,转向,.,更新,d,ij,r,ij,.,对所有,i,j,若,d,ik,+,d,k j,d,ij,则令,d,ij,=,d,ik,+,d,kj,r,ij,=,k,转向,;,终止判断,.,若,k,=,n,终止,;,否则令,k,=,k,+ 1,转向,.,最短路线可由,r,ij,得到,.,26,例 求下图中任意两点间的最短路,.,27,例 设备更新问题,某人购买一台摩托车，准备在今后,4,年内使用，他可在第,1,年初购一台新车，连续使用,4,年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置见下表,1,，不同役龄车的使用维护费及年末处理价见表,2.,要求确定该人使用摩托车的最优更新策略，使,4,年内用于购买、更换及使用维护的总费用为最省。,28,表,2,单位：万元,摩托车役龄（年）,0,1,1,2,2,3,3,4,年使用维护费,0.3,0.5,0.8,1.2,该役龄年末处理费,2,1.6,1.3,1.1,2024/9/21,29,构造有向图，以点,-,表示各年初（同时也是上一年年末），弧（,i,，,j,）旁的数字表示第,i,年初买新车到第,j,年初（即第,j-1,年末）卖掉时的总支出（,i0,则这条链叫相对于流,f,的增广链。,73,当有增广链存在时，找出,再令,74,定理1：流f*是最大流当且仅当网络中没有关于f*的增广链。,定理2：在网络st的最大流量等于它的最小割集的容量。,75,4、求网络最大流的标号算法,76,