图论-数学建模省名师优质课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,1 引言,图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表,“,哥尼斯堡七座桥,”,。,图论中所谓,“,图,”,是指,某类详细事物和这些事物之间联络,。假如我们用,点,表示这些,详细事物,，用连接两点,线段,（直或曲）表示两个,事物特定联络,，就得到了描述这个,“,图,”,几何形象。图论为任何一个包含了一个二元关系离散系统提供了一个数学模型，借助于图论概念、理论和方法，能够对该模型求解。,哥尼斯堡七桥问题就是一个经典例子。在哥尼斯堡有七座桥将普莱格尔河中两个岛及岛与河岸联结起来。问题是,要从这四块陆地中任何一块开始经过每一座桥恰好一次，再回到起点。,第1页,第2页,当然能够经过试验去尝试处理这个问题，但该城居民任何尝试均未成功。,欧拉为了处理这个问题，采取了建立数学模型方法。他将每一块陆地用一个点来代替，将每一座桥用连接对应两点一条线来代替，从而得到一个有,四个,“,点,”,，七条,“,线,”,“,图,”,。问题成为,从任一点出发一笔画出七条线再回到起点,。欧拉考查了普通一笔画结构特点，给出了,一笔画一个判定法则,：,这个图是连通，且每个点都与偶数线相关联，,将这个判定法则应用于七桥问题，得到了,“,不可能走通,”,结果，不但彻底处理了这个问题，而且开创了图论研究先河。,第3页,我们首先经过一些例子来了解网络优化问题。,例1,最短路问题,（SPPshortest path problem）,一名货柜车司机奉命在最短时间内将一车货物从甲地运往乙地。从甲地到乙地公路网纵横交织，所以有各种行车路线，这名司机应选择哪条线路呢？假设货柜车运行速度是恒定，那么这一问题相当于需要找到一条从甲地到乙地最短路。,例2,公路连接问题,某一地域有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都能够经高速公路直接或间接抵达另一个城市。假定已经知道了任意两个城市之间修建高速公路成本，那么应怎样决定在哪些城市间修建高速公路，使得总成本最小？,第4页,例3,指派问题,（assignment problem）一家企业经理准备安排名员工去完成项任务，每人一项。因为各员工特点不一样，不一样员 工去完成同一项任务时所取得回报是不一样。怎样分配工作方案能够使总回报最大？例4,中国邮递员问题,（CPPchinese postman problem）一名邮递员负责投递某个街区邮件。怎样为他 （她）设计一条最短投递路线（从邮局出发，经过投递区内每条街道最少一次，最终返回邮局）？因为这一问题是我国管梅谷教授1960年首先 提，所以国际上称之为中国邮递员问题。,第5页,例5,运输问题,（transportation problem）,某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料工厂。假定个产地产量和家工厂需要量已知，单位产品从任一产地到任一工厂运费已知，那么怎样安排运输方案能够使总运输成本最低？,上述问题有两个共同特点：,一是,它们目标都是从若干可能安排或方案中寻求某种意义下最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；,二是,它们都易于用图形形式直观地描述和表示，数学上把这种与图相关结构称为网络（network）。与图和网络相关最优化问题就是网络最优化或称网络优化（netwok optimization）问题。,第6页,2 图与网络基本概念,2.1 无向图,一个无向图(undirected graph)是由一个非空有限集合 和 中一些元素无序对集合 组成二元组，记为 。,其中 称为,图顶点集,（vertex set）或节点集（node set），中每一个元素,称为该图一个顶点（vertex）或节点（node）；称为,图边集,（edge set），中每一个元素,记为,或 ，被称为该图一条从 到 边（edge）,第7页,一个图称为,有限图,，假如它顶点集和边集都有,限。图顶点数用符号 或 表示，边数用,或 表示。,当讨论图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，比如:分别用 代替 。,端点重合为一点边称为,环(loop),。,一个图称为,简单图,(simple graph)，假如它既没有环也没有两条边连接同一对顶点。,第8页,2.2 有向图,定义 一个有向图（directed graph或 digraph）G是由一个非空有限集合V和V中一些元素有序对集合组成二元组，记为,其中 称为图,顶点集或节点集,.,称为图,弧集,（arc set），A中每一个元素(即中某两个元素有序对),记为,或,，,当弧 时，称为尾（tail），为头（head）.,第9页,2.3 完全图、二分图,每一对不一样顶点都有一条边相连简单图称为,完全图,(complete graph)。n个顶点完全图记为 。,若 ，这里 表示集合X中元素个数），X中无相邻顶点对，Y中亦然，则称G为,二分图,(bipartite graph)；尤其地，若 ，则 ，则称G为,完全二分图,，记成 。,第10页,2.4 子图,假如 ,图H叫做图G子图（subgraph），记作 。若H是G子图，则G称为H母图。,2.5 顶点度,设 ，G中与v关联边数（每个环算作两条边）称为v度(degree)，记作 。若 是奇数，称v是奇顶点(odd point)；若是偶数，称v是偶顶点(even point)。关于顶点度，我们有以下结果：,(i),(ii)任意一个图奇顶点个数是偶数,。,第11页,2.6 图与网络数据结构,网络优化研究是网络上各种优化模型与算法为了在计算机上实现网络优化算法，首先我们必须有一个方法（即数据结构）在计算机上来描述图与网络。,这里我们介绍计算机上用来描述图与网络5种惯用表示方法：,邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。,在下面数据结构讨论中，我们首先假设 是一个简单有向图，并假设V中顶点用自然数1,2,n表示或编号，A中弧用自然数1,2,m表示或编号。,第12页,（i）邻接矩阵表示法,邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）形式存放在计算机中。图 邻接矩阵是以下定义：C是一个n*n0-1矩阵，即,也就是说，假如两节点之间有一条弧，则邻接矩阵中对应元素为1；不然为0。,第13页,例1 对于所表示图，能够用邻接矩阵表示为,一样，对于网络中权，也能够用类似邻接矩阵矩阵表示。只是此时一条弧所对应元素不再是1，而是,对应权,而已。假如网络中每条弧赋有各种权，则能够用多个矩阵表示这些权。,第14页,（ii）关联矩阵表示法,关联矩阵表示法是将图以关联矩阵（incidence matrix）形式存放在计算机中,图 关联矩阵B是以下定义：B是一个n*m矩阵，即,第15页,假如一个节点是一条弧,起点,，则关联矩阵中对应元素为,1,；假如一个节点是一条弧,终点,，则关联矩阵中对应元素为,-1,；假如一个节点与一条弧,不关联,，则关联矩阵中对应元素为,0,。例2 对于例1所表示图，假如关联矩阵中每列对应弧次序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为,（列单位为弧）,第16页,（iii）弧表示法,弧表表示法将图以弧表（arc list）形式存放在计算机中。所谓图弧表，也就是图弧集合中全部有序对。,例3，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上权分别为8，9，6，4，0，3，6和7，则弧表表示以下：,起点,1,1,2,3,4,4,5,5,终点,2,3,4,2,3,5,3,4,权,8,9,6,4,0,3,6,7,第17页,（iv）邻接表表示法,邻接表表示法将图以邻接表（adjacency lists）形式存放在计算机中。,所谓图邻接表，也就是图全部节点邻接表集合；,而对每个节点，它邻接表就是它全部出弧,。邻接表表示法就是对图每个节点，用一个单向链表列出从该节点出发全部弧，链表中每个单元对应于一条出弧。,为了统计弧上权，链表中每个单元除列出弧另一个端点外，还能够包含弧上权等作为数据域,。图整个邻接表能够用一个指针数组表示。,第18页,对于有向图 ，普通用 表示节点邻接表，即节点全部出弧组成集合或链表（实际上只需要列出弧另一个端点，即弧,头）。比如上面例子，等。,第19页,（v）星形表示法,星形（star）表示法思想与邻接表表示法思想有一定相同之处。对每个节点，它也是统计从该节点出发全部弧，但它不是采取单向链表而是采取一个单一数组表示。,统计弧信息数组,弧编号,1,2,3,4,5,6,7,8,起点,1,1,2,3,4,4,5,5,终点,2,3,4,2,3,5,3,4,权,8,9,6,4,0,3,6,7,第20页,3 应用最短路问题,3.1 两个指定顶点之间最短路径,问题以下：给出了一个连接若干个城镇铁路网络，在这个网络两个指定城镇间，找一条最短铁路线。,以各城镇为图G顶点，两城镇间直通铁路为图G对应两顶点间边，得图G。对G每一边e，赋以一个实数,直通铁路长度，称为e权，得到赋权图G。G子图权是指子图G各边权和。,问题就是求赋权图中指定两个顶点 间具最小权轨。这条轨叫做 间最短路，它权叫做 间距离，亦记作 。,第21页,求最短路已经有成熟算法：,迪克斯特拉,（Dijkstra）,算法，其基本思想是按距 从近到远为次序，依次,求得 到G各顶点最短路和距离，直至（或直,至全部顶点），算法结束。为防止重复并保留每,一步计算信息，采取了标号算法。下面是该算法,。,令 ，对 令 ，。,(ii)对每个 ,用 代替,计算 ，把到达这个最小值一个顶点,记为 ，令 。,(iii)若 ，停顿；若 ，用i+1代替,i，转(ii)。,第22页,找出u0到其它各点最短路径,第23页,第24页,3.2 每对顶点之间最短路径,计算赋权图中各对顶点之间最短路径，显然能够调用Dijkstra算法。详细方法是：,每次以不一样顶点作为起点,，用Dijkstra算法求出从该起点到其余顶点最短路径，重复执行次这么操作，就可得到从每一个顶点到其它顶点最短路径。,第二种处理这一问题方法是由Floyd R W提出算法，称之为,Floyd算法。,第25页,假设图权邻接矩阵为，,来存放各边长度，其中：,；,之间没有边，在程序中以各边都不,可能到达充分大数代替；,是 i,j之间边长度，。,第26页,Floyd算法基本思想是：递推产生一个矩阵序列 ，其中 表示从顶点,到顶点 路径上所经过顶点序号小于k,最短路径长度。,计算时用迭代公式：,k是迭代次数，。,最终，当k=n时，即是各顶点之间最短通路值。,(例题见附件),第27页,4 树,4.1 基本概念,连通无圈图叫做树，记之为T。,4.2 应用,连线问题,欲修筑连接n个城市铁路，已知城与城之间铁,路造价为 ，设计一个线路图，使总造价最低。,连线问题数学模型是在连通赋权图上求权最小,生成树。赋权图含有最小权生成树叫做最小生,成树。,第28页,定理 设,G,是含有,n,个顶点图，则下述命题等价：,1),G,是树（,G,无圈且连通）；,2),G,无圈，且有,n,-1,条边；,3),G,连通，且有,n,-1,条边；,4),G,无圈，但添加任一条新边恰好产生一个圈,;,5),G,连通，且删去一条边就不连通了（即,G,为,最,最小连通图,）；,6),G,中任意两顶点间有唯一一条路,.,第29页,找图中生成树方法,可分为两种：避圈法和破圈法,A,避圈法,:,深探法和广探法,B,破圈法,第30页,A,避圈法,这种方法就是在已给图,G,中，每步选出一条边使它与已选边不组成圈，直到选够,n,-1,条边为止,.,这种方法可称为“,避圈法,”或“,加边法,”,在避圈法中，按照边选法不一样，找图中生成树方法可分为两种：,深探法,和,广探法,.,第31页,a),深探法,若这么边另一端均已经有标号，就退到标号为,步骤以下：,i),在点集,V,中任取一点,u,ii),若某点,v,已得标号，检,端是否均已标号,.,若有边,vw,之,w,未标号,则给,w,代,v,，重复,ii).,i,-1,r,点,以,r,代,v,重复,ii),直到全部点得到标号为止,.,给以标号,0.,查一端点为,v,各边，另一,w,以标号,i,+1,，记下边,vw,.,令,0,1,2,3,4,5,6,7,8,9,10,11,12,13,例,用深探法求出下列图,10,一棵生成树,第32页,b),广探法,步骤以下：,i),在点集,V,中任取一点,u,ii),令全部标号,i,点集为,是否均已标号,.,对全部未标,号之点均标以,i,+1,记下这些,iii),对标号,i,+1,点重复步,步骤,ii),，直到全部点得到,给u,以标号,0.,V,i,检验,V,i,VV,i,中边端点,边,.,例,用广探法求出下列图,10,一棵生成树,标号为止,.,图,10,3,1,0,1,2,2,1,3,2,1,2,2,3,4,第33页,B,破圈法,相对于避圈法，还有一个求生成树方法叫做,“,破圈法,”,.,这种方法就是在图,G,中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图,G,中没有圈为止,.,例,用破圈法求出,下列图一棵生成树,.,图生成树不是唯一,.,第34页,A,Kruskal,算法（或避圈法）,步骤以下：,1),选择边,e,1,，使得,w(e,1,),尽可能小；,2),若已选定边 ，则从,中选取 ，使得,:,i),为无圈图，,ii),是满足,i),尽可能小权，,3),当第,2),步不能继续执行时，则停顿,.,定理,4,由,Kruskal,算法构作任何生成树,都是最小树,.,最小生成树与算法,第35页,例,用,Kruskal,算法求下列图最小树,.,在左图中 权值,最小边有 任取一条,在 中选取权值,最小边,中权值最小边有,从中选,任取一条边,会与已选边组成圈,故停顿,得,中选取在中选取,中选取,.,但 与 都,第36页,B,破圈法,算法,2,步骤以下：,1),从图,G,中任选一棵树,T,1,.,2),加上一条弦,e,1,，,T,1,+e,1,中,马上生成一个圈,.,去掉此,圈中最大权边，得到新,树,T,2,以,T,2,代,T,1,重复,2),再,检验剩下弦，直到全,部弦检验完成为止,.,例,用破圈法求下列图最小树,.,第37页,prim,算法结构最小生成树,设置两个集合,P和Q,其中P用于存放最小生成,树G中顶点，集合Q存放最小生成树G中边。令,集合P初值为 （假设结构最小生成树时，从,顶点 出发），集合Q初值为 。,prim算法思想是,，从全部 ，边,中，选取含有最小权值边 ，将顶点v加入,集合P中，将边pv加入集合Q中，如此不停重复，直,到 P=V 时，最小生成树结构完成，这时集合Q中包,含了最小生成树全部边。,第38页,例11 用prim算法求右图最小生成树。,我们用第一二、三行分别表示生成树边起点、终点、权集合。,Matlab程序以下：,clc;clear;,M=1000;,a(1,2)=50;a(1,3)=60;,a(2,4)=65;a(2,5)=40;,a(3,4)=52;a(3,7)=45;,a(4,5)=50;a(4,6)=30;a(4,7)=42;,a(5,6)=70;,a=a;zeros(2,7);,a=a+a;a(find(a=0)=M;,result=;p=1;tb=2:length(a);,while length(result)=length(a)-1,result=,temp=a(p,tb);temp=temp(:);,1 2 5 4 4 7,d=min(temp);,2 5 4 6 7 3,jb,kb=find(a(p,tb)=d);,50 40 50 30 42 45,j=p(jb(1);k=tb(kb(1);,result=result,j;k;d;p=p,k;tb(find(tb=k)=;,end,result,第39页,例 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应怎样安排旅游线，使旅程最短？各城市之间航线距离以下表,：,L,M,N,Pa,Pe,T,L,56,35,21,51,60,M,56,21,57,78,70,N,35,2136,68,68,Pa,21,57,36,51,61,Pe,51,78,68,51,13,T,60,70,68,61,13,第40页,解：编写程序以下：,clc,clear,a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;,a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;,a(3,4)=36;a(3,5)=68;a(3,6)=68;,a(4,5)=51;a(4,6)=61;,a(5,6)=13;,a(6,:)=0;,a=a+a;,c1=5 1:4 6;,L=length(c1);,flag=1;,while flag0,flag=0;,for m=1:L-3,for n=m+2:L-1,if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0,flag=0;,for m=1:L-3,for n=m+2:L-1,if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).,a(c1(m),c1(m+1)+a(c1(n),c1(n+1),flag=1;,c1(m+1:n)=c1(n:-1:m+1);,end,end,end,end,sum1=0;,for i=1:L-1,sum1=sum1+a(c1(i),c1(i+1);,end,if sum1sum,sum=sum1;,circle=c1;,end,circle,sum,第42页,