欢迎来到天天文库
浏览记录
ID:37220346
大小:3.11 MB
页数:67页
时间:2019-05-19
《关于正则图的圈边连通度判定算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、论文题目:关于J下则图的圈边连通度判定算法专业:计算机软件与理论硕士生:梁康奇指导教师:娄定俊教授摘要一个网络可以用一个连通图来表示,其中图的顶点表示网络中的组件,边表示两个组件之间的通信信道。图的连通度可以衡量网络的稳定性。一般来说,一个图的连通性越好,它所代表的网络越稳定。然两,连通度衡量网络的可靠性是有缺陷的。于是,学者们先后引入各种连通度,包括圈边连通度。与连通度相比,圈边连通度不受图的最小度限制,从而可以更好地衡量网络的连通性。长期以来,关于一般图的圈边连通度判定是否为P问题还没有得到解决。LOU和wANG[1]给
2、出了第一个关于K正则图的圈边连通度的判定算法,其时间复杂度是O(k¨IVl8),此复杂度在实际应用中稍大。因此,进一步提高算法的执行效率具有重要意义,也是本文要研究的问题。本文设计酶改进算法将在前人工作的基础上,通过对正则图的结构作更深入细致的分析,来达到改进算法的目的,新算法的时间复杂度是O(k9Ivl6)。在研究的过程中,我们证明了以下一个引理:引理4。2.1图G是连通的k-正剡图。如果瓿(G><丞-2)g,则测除一个最小圈边割S,G.S有两个连通分支,每一个连通分支各包含一个圈C。如果C是奇圈,则I矿(oI<2Llog
3、纠v(O)J+S;如果C是偶圈,则Iy(C)阵2[109Hv(G)J+6。本文第一部分会绍图的连通度的研究现状和进展,指出本文的选题背景和研究意义。第二部分综述本文所需要的预备知识,包括一些关于图的基本概念和专业术语,有关连通度的一些基本结论和一些引理。第三部分基于文献E1]关于3一正则图的圈边连通度判定算法设计我们的改进算法,并且在理论上证明薪算法的正确性,以及新算法的时间复杂度分析。第四部分把3一正则图的改进算法推广到l(一正则图的情形,并且实现该算法。关键词:圈边连通度、芷则图、连通度、围长关于聂襄鹜的麟透连通度翔定葬
4、滚AbstractTitle:Major:Name:AnAlgorithmforCyclicEdgeConnectivityofRegularGraphsComputerSoftwareandTheoryKangqiLiangSupervisor:Prof.DingjunLouAbstractAnetworkcanberepresentedbyasimpleandconnectedgraphG(VE),whereeachvertexV∈Vrepresentsacomponent,andeachedgeOl'磅£嚣repres
5、entsalinkbetweentheverticesUandV:Theconnectivityisanimportantmeasureforreliabilityofthenetwork.Ingeneral,thelargerconnectivityis,themorereliablethenetworkis.Measuringreliabili移ofanetworkbyconnectivityisflawed.Toovercomesuchshortcoming,Scholarsinroducedotherconcepts
6、ofconditionalconnectivityincludingcyclicedgeconnectivity.Comparedwithconnectivity,cyclicedgeconnectivityisnotboundedbyminimumdegreeofGSOthatitCallmeasurereliabilityinabetterway.1tisalongstandingunsolvedproblemwhethertodeterminethecycliccdgeconnectivityofagraphisaP-
7、problem.LouandWang[1]obtainedthefirstefficientalgorithmtoderterminethecyclicedgeconnectivityofk-regulargraphs.However,thetimecomplecxityofthefirstalgorithmisO(kHIVls)whichalittletoolargeforpracticaluse.Therefore,improvingtheefficiencyofalgorithmissignificant,whichi
8、salsotheproblemthatthispapersolves。Thenewalgorithmisbasedontheformerresearch.Weimprovetheoriginalalgorithmbyanalysingthestructureofregulargraphsm
此文档下载收益归作者所有