最小支撑树算法及应用的论文

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

安庆师范学院数学与计算科学学院2012届毕业论文第1页共11页最小支撑树算法及应用作者:指导老师:摘要求解最小支撑树通常采用破圈法和避圈法,其基本原理是使其成为权数之和为最小的连通图。根据此原理,引出两种新的算法,称为最小权数保留法和最大权数去除法.利用最小支撑树合理地进行电网规划可以获得巨大的社会效益和经济效益。论文针对电网规划的特点,利用最小支撑树对电网进行优化。关键词最小支撑树破圈法避圈法1最小支撑树的三种算法图论中的图是由点和边所构成,用以反映一些对象之间的关系。若所有点的集合为V,所有边的集合为E,则图G=(V,E)。给图G的每一条边加上一个非负的实数,则称图G为赋权图。若有图111,GVE,222,GVE,333,GVE,444,GVE,其中1234VVVV,{1234,,,EEEE}E,且1234,,,GGGG为树,则1234,,,GGGG被称为图G的生成树。若2G具有最小权,则称2G为图G的最小支撑树。求解最小生成树常用的方法是Krukal(避圈法)法和破圈法。无论破圈法还是避圈法,都存在一个核心问题——图形必须正确绘制出来。只有在正确绘制出图形的基础上才能用避圈法或破圈法得到准确的最小支撑树(kruskal)和破圈法等求解方法1.1算法一:Kruskal算法(也就是避圈法)算法一的中心思想是每次添加权尽可能小的边,使新的图无圈,直至得到支撑树为止该方法形象地简称为最小边加入法其步骤如下:(1)把N内的所有的边按照权的大小由小到大排列(2)按(1)排列的次序依次检查N中的每一条边,如果这条边与已得到的图不产生圈,则取这一条边为所求支撑树的一部分(3)若已取到n-1条边,算法终止此时以V为顶点集,以取所取的n-1条边为边集的图即为最小支撑树例1求图1所示网络的最小支撑树解将各边的权按非减次序排列,得网络中的8条边的排列次序为1238eeee首先取权最小的两条边1e和2e为所求最小支撑树T的两条边,然后检查边3e由于边1e2e和3e构成圈,故不取边3e接下来考虑边4e由于1e2e和4e不构成圈,故取4e然后检查边e5由于1e2e4e和5e不构成圈,故取5e再看6e,它与4e5e构成圈,安庆师范学院数学与计算科学学院2012届毕业论文第2页共11页故不取同样地7e,8e也不可取,因为7e与2e,4e,5e构成圈,而8e与2e,5e构成圈因此由1e,2e,4e和5e构成的支撑树T为网络N的最小支撑树(如下图所示)示1.2.算法二(普赖姆,Prim)这是一种迭代算法,每进行一次迭代将产生组成网络N最小支撑树T的一条边其做法基于下面的事实:如果我们已经知道T中的一些边,它们的端点组成点集S,S是N的顶点集V的一个子集以s记一个端点在S中另一端点在V\S中的所有边组成的集合因为最小支撑树T是N的连通生成子图,必有边连接点集S和点集V\S内的点,这样,(S)中权最小的一条边也应该是N的最小支撑树T中的一条边。设V(G)=12,,,nvvv,ijijevvEGijijwwe为边ije的权如果iv与jv之间无边相连,则取ijw为叙述方便,我们以顶点的下标来表示S中的顶点普赖姆迭代过程:(1)T=,S={1},R={2,3,,n},jijUw,此处i=1S,jR(2)设minjikUw,记jikUw以S{k}代替S,R\{k}代替R,T{ike}代替T(3)若R=,算法终止,此时T即为所求;否则,对每个jR,以min{,jikUw|kS}代替jU,返回上一步骤(2)例2求图1所示的网络N的最小支撑树T我们用图显示普赖姆方法的各步骤,在图中标出该步骤应该考虑的各边的权,不标出不需考虑的边的权,在该步骤中取的点画有叉号,边画成稍微加粗的,该步骤前已经取的点和边画成最粗的(1)算法开始时,S={1v},(S)={1e,3e}因为w(1e)=12=w(3e),所以取T={1e}安庆师范学院数学与计算科学学院2012届毕业论文第3页共11页(2)把1e不在S中的一个端点v2加入到S中,于是S={1v,2v},(S)=2356eeee,(S)中权最小的边为2e和3e,任取一条边,例如把3e加到T中,则T={1e,3e}(3)把3e不在S中的另一端点3v加进S中,此时S={123,,vvv},(S)={5e,67,ee,8e},其中权最小的边为5e,取T={1e,3e,5e}(4)把5e不在S中的一端点5v加入S,S={123,,vvv6712354,,,,,eevvvvv5v},(S)={4e,67,ee},其中权最小的边为4e,从而取T={1e,3e,5e,4e}(5)把4e不在S中的一个端点4v加进S中,此时S={12354,,,,vvvvv}=V,V\S=,故算法终止此时以V为顶点集T={1e,3e,5e,4e}为边集的树T即为N的最小支撑树1.3算法三:破圈法破圈法就是在图中任意取一个圈,从圈中去掉权最大的边,将这个圈破掉重复这个过程,直到图中没有圈为止,保留下的边组成的图即为最小支撑树其算法基本步骤如下:(1)从图G中任选一棵树1T(2)加上一条弦1e,1T+1e中立即生成一个圈去掉此权中最大权边,得到新树2T以安庆师范学院数学与计算科学学院2012届毕业论文第4页共11页2T代替1T,重复(2)再检查剩余的弦,直到全部弦检查完毕为止例3用破圈法求图1所示网络的最小支撑树图(3)解:在圈321vvv中,去掉权最大的边3e,得图(a);在圈542vvv中,去掉权最大的边6e,得图(b);在圈543vvv中,去掉权最大的边7e,得图(c);在圈5321vvvv中,去掉权最大的边8e,得图(d)此时,在图(d)中已经没有圈了,于是得最小支撑树2对最小支撑树的两种捷径算法的探讨2.1概念回顾图是由点和边所构成,用以反映一些对象之间的关系。若所有点的集合为V,所有边的集合为E,则图G=(V,E)。给图G的每一条边加上一个非负的实数,则称图G为赋权图。若有图111,GVE,222,GVE,333,GVE,444,GVE,其中,1234VVVV,{1234,,,EEEE}E,且1234,,,GGGG为树,则1234,,,GGGG被称为图G的生成树。若2G具有最小权,则称2G为图G的最小生成树。求解最小生成树常用的方法是Krukal(避圈法)法和破圈法。无论破圈法还是避圈法,都存在一个核心问题——图形必须正确绘制出来。只有在正确绘制出图形的基础上才能用避圈法或破圈法得到准确的最小支撑树。安庆师范学院数学与计算科学学院2012届毕业论文第5页共11页2.2捷径算法支撑树有一个核心原理——所有的点都至少有一条边连接,并且只要该点被纳入图中则不再重复连接。如下图:图(a)是支撑树,因为所有的点都包含在图中,并且每个点都至少有一条边相连,而且不重复;图(b)不是支撑树,虽然所有的点都包含在图中,并且每个点至少有一条边相连,但点与点之间的连线进行了点的重复联结,故图(b)不是支撑树;图(c)不是支撑树,因点与点之间的连线未被纳入整个图形中,与其他点之间是断开的,则被视为是两个图形,若连接与,则图形被称为支撑树。而最小支撑树是所有权数之和为最小的支撑树图,支撑树不唯一,但最小支撑树是唯一的。由此原理,引申出两种求解最小支撑树的算法,该种算法既可以在已知图形的基础上很快的得出最小支撑树图,也可以在未知图形的基础上得出最小支撑树图。2.3最小权数保留法(1)基本思路。首先,在所有的权数中选取最小权数的边,连接两点;其次,在剩下的权数中选取次小的,连接两点;依此类推,最后,使所有连接构成在一个图形上,成为一个连通图,则该图就是最小支撑树图。(2)支撑理论。定理1:任意图G有支撑树的充分必要条件是图G是连通的。定理2:图G=(V,E)是一个树的充分必要条件是G是连通图,并且,其中N为点的个数。(3)算法步骤。第1步:从图G中选取一条权数最小的边,连接两点,记为112,EVV;第2步:在从剩下的权数中选取次小的边,连接两点,记为234,EVV;第3步:重复1、2步,直到1EN;第4步:如果NPG,则',ijGVE为图的最小支撑树。(4)算法举例。现为一乡镇中各村庄架设电线,图中各点为村庄,边为各村庄之间的连通关系,边上的权代表架设电线的耗材。现在要求用电线把所有村庄联系起来,如何设计可使架设电线耗材最省。解:从图G所有权数中选取权数最小的边56,VV,连接56,VV两点,记为15656,GVE,E=1,N=2;从剩下的权数中选取权数次小的边35,VV,连接35,VV两点,记为23535,GVE,E=2,N=3;再次从剩下的权数中选取权数次小的边12,VV连接12,VV两点,记为31212,GVE,安庆师范学院数学与计算科学学院2012届毕业论文第6页共11页E=3,N=4;再次从剩下的权数中选取权数次小的边47,VV,连接47,VV两点,记为44747,GVE,E=4,N=5;在从剩下的权数中选择权数次小的边24,VV,连接24,VV两点,记为52727,GVE,E=5,N=6;最后选择权数次小的边34,VV,连接34,VV两点,记为63434,GVE,E=6,N=7则得到最小支撑树。2.4最大权数去除法(1)基本思路。在所有的权数中选取最大权数的边,去除该边,依次检查所有的边,在所有的点保持连通的情况下,删除最大的边,直到E=N-1为止,则该图就是最小支撑树图。(2)支撑理论。定理1:任意图G有支撑树的充分必要条件是图G是连通的。定理2:图G=(V,E)是一个树的充分必要条件是G是连通图,并且其中N为点的个数。(3)算法步骤。第1步:从图G中选取一条权数最大的边,去除该边;第2步:在保证各点连通的情况下,从剩下的权数中选取最大的边去除;第3步:重复1、2步,直到;则',ijGVE为图的最小支撑树。(4)算法举例。设计如图所示的锅炉房到各座楼铺设暖气管道的路线,使管道总长度最小(单位:M)解:从图中选取权数最大的边{A,2},记为E={A,2},并将该边予以去除;选取权数次大的边{4,10},记为E={4,10},并将该边予以去除;在保证连通的情况下,重复上述步骤,直至E=N-1,计算结束,得到最小支撑树。安庆师范学院数学与计算科学学院2012届毕业论文第7页共11页3最小支撑树的一种删除大权边算法及应用最小支撑树的一种删除大权边算法是在Kruskal算法、Prim算法和破圈法的基础上,提出的另一种算法。介绍了删除大权边算法的基本概念和性质,列举了删除大权边算法的计算实例,叙述了删除大权边算法的及其应用。随着科学技术的迅速发展,20世纪50年代图论得到进一步发展。将庞大复杂的系统工程和管理问题用图描述,可以解决许多工程设计和管理决策的最优化问题。如,各种通信网络的合理设计交通网络的合理分布、线路的优化设计和管道网络最优铺设等,通过对图的研究,达到研究系统的目的,由于其模型简单而实用,对实际问题的描述具有直观性,所以,它在许多科学领域中得到广泛的应用。3.1基本概念和性质树是图论中的一个重要基本概念,它具有广泛的实用性。下面就有关的概念和性质作一简要探讨。定义1:连通的无圈图称为树。定义2:图G=(V,E),对G中的每一条边uv,相应的有一个数W,则称这一图G为赋权图,W为uv边上的权。定义3:权是指与边有关的数量指标。根据实际应用可以赋予不同的实际意义,如,距离、时间和费用等。赋权图在图的理论及其应用方面有着重要的地位,赋权图不仅指各个点之间的邻接关系,而且同时也表示各点之间的数量关系。所以,赋权图被广泛应用于解决工程技术及科学生产管理等诸多领域的最优化问题,最小支撑树问题即是赋权图上的最优化问题。最小支撑树模型概括为:给定网络中一些点和这些点之间的距离,寻找连接所有这些点的最小总距离。即,求G的一棵支撑

1 / 11
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功