关于正则图圈边连通度判定算法

《关于正则图圈边连通度判定算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文关于正则图的圈边连通度判定算法姓名：梁康奇申请学位级别：硕士专业：计算机软件与理论指导教师：娄定俊20090525论文题目：专业：硕士生：指导教师：关于J下则图的圈边连通度判定算法计算机软件与理论梁康奇娄定俊教授摘要一个网络可以用一个连通图来表示，其中图的顶点表示网络中的组件，边表示两个组件之间的通信信道。图的连通度可以衡量网络的稳定性。一般来说，一个图的连通性越好，它所代表的网络越稳定。然两，连通度衡量网络的可靠性是有缺陷的。于是，学者们先后引入各种连通度，包括圈边连通度。与连通度相比，圈边连通度不受图的最小度限制，从而可以更好地衡量网络的连通性。

2、长期以来，关于一般图的圈边连通度判定是否为P问题还没有得到解决。LOU和wANG[1]给出了第一个关于K正则图的圈边连通度的判定算法，其时间复杂度是O(k¨IVl8)，此复杂度在实际应用中稍大。因此，进一步提高算法的执行效率具有重要意义，也是本文要研究的问题。本文设计酶改进算法将在前人工作的基础上，通过对正则图的结构作更深入细致的分析，来达到改进算法的目的，新算法的时间复杂度是O(k9Ivl6)。在研究的过程中，我们证明了以下一个引理：引理4。2．1图G是连通的k-正剡图。如果瓿(G><丞-2)g，则测除一个最小圈边割S，G．S有两个连通分支，每一个连通分支各包含一个圈

3、C。如果C是奇圈，则I矿(oI<2Llog纠v(O)J+S；如果C是偶圈，则Iy(C)阵2[109Hv(G)J+6。本文第一部分会绍图的连通度的研究现状和进展，指出本文的选题背景和研究意义。第二部分综述本文所需要的预备知识，包括一些关于图的基本概念和专业术语，有关连通度的一些基本结论和一些引理。第三部分基于文献E1]关于3一正则图的圈边连通度判定算法设计我们的改进算法，并且在理论上证明薪算法的正确性，以及新算法的时间复杂度分析。第四部分把3一正则图的改进算法推广到l(一正则图的情形，并且实现该算法。关键词：圈边连通度、芷则图、连通度、围长关于聂襄鹜的麟透连通度翔定葬滚A

4、bstractTitle：Major：Name：AnAlgorithmforCyclicEdgeConnectivityofRegularGraphsComputerSoftwareandTheoryKangqiLiangSupervisor：Prof．DingjunLouAbstractAnetworkcanberepresentedbyasimpleandconnectedgraphG(VE)，whereeachvertexV∈Vrepresentsacomponent,andeachedgeOl'磅￡嚣representsalinkbetweenthevertic

5、esUandV：Theconnectivityisanimportantmeasureforreliabilityofthenetwork．Ingeneral，thelargerconnectivityis，themorereliablethenetworkis．Measuringreliabili移ofanetworkbyconnectivityisflawed．Toovercomesuchshortcoming，Scholarsinroducedotherconceptsofconditionalconnectivityincludingcyclicedgeconn

6、ectivity．Comparedwithconnectivity,cyclicedgeconnectivityisnotboundedbyminimumdegreeofGSOthatitCallmeasurereliabilityinabetterway．1tisalongstandingunsolvedproblemwhethertodeterminethecycliccdgeconnectivityofagraphisaP-problem．LouandWang[1]obtainedthefirstefficientalgorithmtoderterminethec

7、yclicedgeconnectivityofk-regulargraphs．However,thetimecomplecxityofthefirstalgorithmisO(kHIVls)whichalittletoolargeforpracticaluse．Therefore,improvingtheefficiencyofalgorithmissignificant，whichisalsotheproblemthatthispapersolves。Thenewalgorithmisbasedontheformerresearch．W