下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 图论-数学建模

图论-数学建模.ppt

图论-数学建模

天命彩蝶
2010-09-03 0人阅读 举报 0 0 暂无简介

简介:本文档为《图论-数学建模ppt》,可适用于人文社科领域

图论图论山东建筑大学贺长伟引言引言图论起源于世纪。第一篇图论论文是瑞士数学家欧拉于年发表的“哥尼斯堡的七座桥”。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物用连接两点的线段(直的或曲的)表示两个事物的特定的联系就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型借助于图论的概念、理论和方法可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次再回到起点。当然可以通过试验去尝试解决这个问题但该城居民的任何尝试均未成功。欧拉为了解决这个问题采用了建立数学模型的方法。他将每一块陆地用一个点来代替将每一座桥用连接相应两点的一条线来代替从而得到一个有四个“点”七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点给出了一笔画的一个判定法则:这个图是连通的且每个点都与偶数线相关联将这个判定法则应用于七桥问题得到了“不可能走通”的结果不但彻底解决了这个问题而且开创了图论研究的先河。我们首先通过一些例子来了解网络优化问题。例最短路问题(SPP-shortestpathproblem)一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错因此有多种行车路线这名司机应选择哪条线路呢?假设货柜车的运行速度是恒定的那么这一问题相当于需要找到一条从甲地到乙地的最短路。例公路连接问题某一地区有若干个主要城市现准备修建高速公路把这些城市连接起来使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本那么应如何决定在哪些城市间修建高速公路使得总成本最小?例指派问题(assignmentproblem)一家公司经理准备安排名员工去完成项任务每人一项。由于各员工的特点不同不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大?例中国邮递员问题(CPP-chinesepostmanproblem)一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从邮局出发经过投递区内每条街道至少一次最后返回邮局)?由于这一问题是我国管梅谷教授年首先提的所以国际上称之为中国邮递员问题。例指派问题(assignmentproblem)一家公司经理准备安排名员工去完成项任务每人一项。由于各员工的特点不同不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大?例中国邮递员问题(CPP-chinesepostmanproblem)一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从邮局出发经过投递区内每条街道至少一次最后返回邮局)?由于这一问题是我国管梅谷教授年首先提的所以国际上称之为中国邮递员问题。例运输问题(transportationproblem)某种原材料有个产地现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知单位产品从任一产地到任一工厂的运费已知那么如何安排运输方案可以使总运输成本最低?上述问题有两个共同的特点:一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案数学上把这种问题称为最优化或优化(optimization)问题二是它们都易于用图形的形式直观地描述和表达数学上把这种与图相关的结构称为网络(network)。与图和网络相关的最优化问题就是网络最优化或称网络优化(netwokoptimization)问题。图与网络的基本概念图与网络的基本概念无向图一个无向图(undirectedgraph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组记为。其中称为图的顶点集(vertexset)或节点集(nodeset)中的每一个元素称为该图的一个顶点(vertex)或节点(node)称为图的边集(edgeset)中的每一个元素 记为或被称为该图的一条从到的边(edge)一个图称为有限图如果它的顶点集和边集都有限。图的顶点数用符号或表示边数用或表示。当讨论的图只有一个时总是用G来表示这个图。从而在图论符号中我们常略去字母G例如:分别用代替。端点重合为一点的边称为环(loop)。一个图称为简单图(simplegraph)如果它既没有环也没有两条边连接同一对顶点。有向图定义一个有向图(directedgraph或digraph)G是由一个非空有限集合V和V中某些元素的有序对集合构成的二元组记为其中称为图的顶点集或节点集称为图的弧集(arcset)A中的每一个元素(即中某两个元素的有序对) 记为或当弧时称为尾(tail)为头(head)完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。n个顶点的完全图记为。若(这里表示集合X中的元素个数)X中无相邻顶点对Y中亦然则称G为二分图(bipartitegraph)特别地若则则称G为完全二分图记成。子图如果,,图H叫做图G的子图(subgraph)记作。若H是G的子图则G称为H的母图。顶点的度设G中与v关联的边数(每个环算作两条边)称为v的度(degree)记作。若是奇数称v是奇顶点(oddpoint)若是偶数称v是偶顶点(evenpoint)。关于顶点的度我们有如下结果:(i)(ii)任意一个图的奇顶点的个数是偶数。图与网络的数据结构图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法.为了在计算机上实现网络优化的算法首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。这里我们介绍计算机上用来描述图与网络的种常用表示方法:邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中我们首先假设是一个简单有向图并假设V中的顶点用自然数,,…n表示或编号A中的弧用自然数,,…m表示或编号。(i)邻接矩阵表示法(i)邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵(adjacencymatrix)的形式存储在计算机中。图的邻接矩阵是如下定义的:C是一个n*n的矩阵即也就是说如果两节点之间有一条弧则邻接矩阵中对应的元素为否则为。例对于所示的图可以用邻接矩阵表示为同样对于网络中的权也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是而是相应的权而已。如果网络中每条弧赋有多种权则可以用多个矩阵表示这些权。(ii)关联矩阵表示法(ii)关联矩阵表示法关联矩阵表示法是将图以关联矩阵(incidencematrix)的形式存储在计算机中.图的关联矩阵B是如下定义的:B是一个n*m的矩阵即如果一个节点是一条弧的起点则关联矩阵中对应的元素为如果一个节点是一条弧的终点则关联矩阵中对应的元素为如果一个节点与一条弧不关联则关联矩阵中对应的元素为。例对于例所示的图如果关联矩阵中每列对应弧的顺序为(,)(,)(,)(,)(,)(,)(,)和(,)则关联矩阵表示为(列单位为弧)(iii)弧表示法(iii)弧表示法弧表表示法将图以弧表(arclist)的形式存储在计算机中。所谓图的弧表也就是图的弧集合中的所有有序对。例假设弧(,)(,)(,)(,)(,)(,)(,)和(,)上的权分别为和则弧表表示如下:(iv)邻接表表示法(iv)邻接表表示法邻接表表示法将图以邻接表(adjacencylists)的形式存储在计算机中。所谓图的邻接表也就是图的所有节点的邻接表的集合而对每个节点它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点用一个单向链表列出从该节点出发的所有弧链表中每个单元对应于一条出弧。为了记录弧上的权链表中每个单元除列出弧的另一个端点外还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。对于有向图一般用表示节点的邻接表即节点的所有出弧构成的集合或链表(实际上只需要列出弧的另一个端点即弧的头)。例如上面例子等。(v)星形表示法(v)星形表示法星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点它也是记录从该节点出发的所有弧但它不是采用单向链表而是采用一个单一的数组表示。记录弧信息的数组§应用最短路问题§应用最短路问题两个指定顶点之间的最短路径问题如下:给出了一个连接若干个城镇的铁路网络在这个网络的两个指定城镇间找一条最短铁路线。以各城镇为图G的顶点两城镇间的直通铁路为图G相应两顶点间的边得图G。对G的每一边e赋以一个实数直通铁路的长度称为e的权得到赋权图G。G的子图的权是指子图G的各边的权和。问题就是求赋权图中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路它的权叫做间的距离亦记作。求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法其基本思想是按距从近到远为顺序依次求得到的G各顶点的最短路和距离直至(或直至的所有顶点)算法结束。为避免重复并保留每一步的计算信息采用了标号算法。下面是该算法。令对令。(ii)对每个,用代替计算把达到这个最小值的一个顶点记为令。(iii)若停止若用i代替i转(ii)。找出u到其他各点的最短路径找出u到其他各点的最短路径每对顶点之间的最短路径每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径显然可以调用Dijkstra算法。具体方法是:每次以不同的顶点作为起点用Dijkstra算法求出从该起点到其余顶点的最短路径反复执行次这样的操作就可得到从每一个顶点到其它顶点的最短路径。第二种解决这一问题的方法是由FloydRW提出的算法称之为Floyd算法。假设图权的邻接矩阵为来存放各边长度其中:之间没有边在程序中以各边都不可能达到的充分大的数代替是i,j之间边的长度。Floyd算法的基本思想是:递推产生一个矩阵序列其中表示从顶点到顶点的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式:k是迭代次数。最后当k=n时即是各顶点之间的最短通路值。(例题见附件)§树§树基本概念连通的无圈图叫做树记之为T。应用连线问题欲修筑连接n个城市的铁路已知城与城之间的铁路造价为设计一个线路图使总造价最低。连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。定理设G是具有n个顶点的图则下述命题等价:)G是树(G无圈且连通))G无圈且有n条边)G连通且有n条边)G无圈但添加任一条新边恰好产生一个圈)G连通且删去一条边就不连通了(即G为最最小连通图))G中任意两顶点间有唯一一条路找图中生成树的方法找图中生成树的方法可分为两种:避圈法和破圈法A避圈法:深探法和广探法B破圈法A避圈法这种方法就是在已给的图G中每步选出一条边使它与已选边不构成圈直到选够n条边为止这种方法可称为“避圈法”或“加边法”在避圈法中按照边的选法不同找图中生成树的方法可分为两种:深探法和广探法a)深探法若这样的边的另一端均已有标号就退到标号为步骤如下:i)在点集V中任取一点u,ii)若某点v已得标号检端是否均已标号若有边vw之w未标号,则给w代v重复ii)i的r点,以r代v,重复ii),直到全部点得到标号为止给以标号查一端点为v的各边另一w以标号i记下边vw令例用深探法求出下图的一棵生成树b)广探法步骤如下:i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号对所有未标号之点均标以i,记下这些iii)对标号i的点重复步步骤ii)直到全部点得到给u以标号Vi,检查Vi,VVi中的边端点边例用广探法求出下图的一棵生成树标号为止B破圈法相对于避圈法还有一种求生成树的方法叫做“破圈法”这种方法就是在图G中任取一个圈任意舍弃一条边将这个圈破掉重复这个步骤直到图G中没有圈为止例用破圈法求出下图的一棵生成树图的生成树不是唯一的AKruskal算法(或避圈法)步骤如下:)选择边e使得w(e)尽可能小)当第)步不能继续执行时则停止定理由Kruskal算法构作的任何生成树最小生成树与算法例用Kruskal算法求下图的最小树会与已选边构成圈,故停止,得B破圈法算法步骤如下:)从图G中任选一棵树T)加上一条弦eTe中立即生成一个圈去掉此圈中最大权边得到新树T,以T代T,重复)再检查剩余的弦直到全部弦检查完毕为止例用破圈法求下图的最小树prim算法构造最小生成树设置两个集合P和Q,其中P用于存放的最小生成树G中的顶点集合Q存放的最小生成树G中的边。令集合P的初值为(假设构造最小生成树时从顶点出发)集合Q的初值为。prim算法的思想是从所有的边中选取具有最小权值的边将顶点v加入集合P中将边pv加入集合Q中如此不断重复直到P=V时最小生成树构造完毕这时集合Q中包含了最小生成树的所有边。例用prim算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下:clcclearM=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a=azeros(,)a=aa'a(find(a==))=Mresult=p=tb=:length(a)whilelength(result)~=length(a)result=temp=a(p,tb)temp=temp(:)d=min(temp)jb,kb=find(a(p,tb)==d)j=p(jb())k=tb(kb())result=result,jkdp=p,ktb(find(tb==k))=endresult例从北京(Pe)乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游每城市恰去一次再回北京应如何安排旅游线使旅程最短?各城市之间的航线距离如下表:解:编写程序如下:clc,cleara(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,)=a(,:)=a=aa'c=:L=length(c)flag=whileflag>flag=form=:Lforn=m:Lifa(c(m),c(n))a(c(m),c(n))<a(c(m),c(m))a(c(n),c(n))flag=c(m:n)=c(n::m)endendendendsum=fori=:Lsum=suma(c(i),c(i))endcircle=csum=sumc=:改变初始圈该算法的最后一个顶点不动flag=whileflag>flag=form=:Lforn=m:Lifa(c(m),c(n))a(c(m),c(n))<a(c(m),c(m))a(c(n),c(n))flag=c(m:n)=c(n::m)endendendendsum=fori=:Lsum=suma(c(i),c(i))endifsum<sumsum=sumcircle=cendcircle,sum

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/43

图论-数学建模

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利