关于图的k阶限制边连通度一些问题的研究

《关于图的k阶限制边连通度一些问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据ThesisfortheMaster’SDegree，ShanxiUniversity,2012Researchabout恐一restrictededgeconnectivityingraphsStudentNameBenWangSupervisorProf．ShiyingWangMajorAppliedMathematicsFieldofResearchGraphTheoryandApplicationDepartmentSchoolofMathematicalSciencesR．esea

2、rchDuration2009．09—2012．06June，2012万方数据目录中文摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．iAbstract．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．，．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．ii引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。l第一章预备知识⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．2第二章A5．最优图的一个充分条件⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

3、⋯⋯⋯3第三章k一最优图的一个度条件⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯‘⋯⋯．．11结束语⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯23参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯24研究成果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯27个人简况及联系方式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28承诺书⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯29学位论文使用授权声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯30万方数据Contents』kbstractinChinese⋯．．．．⋯⋯⋯．⋯．．．．．．．．．．．Abstract．．．．．．．．．．．⋯⋯⋯⋯⋯⋯．⋯⋯⋯．⋯⋯．．．⋯．．．．．．⋯．IntroductionChapter1Preliminary．，．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．2Chapter2Asufficientconditionfor砖-optimalgraphs．．3Chapter3Adegr

5、eeconditionforA4-optimalgraphs⋯⋯⋯⋯⋯⋯⋯⋯．．1lConclusion．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．23References．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．⋯．．．．．．．．．．．．．．．．．．．．．．，．．．．．．．：}4PublishedArticlesDirectory⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯．⋯．⋯．

6、．，⋯⋯．26Acknowledgements⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．⋯．27PersonalInformation．．．．．．．．．．。．．．．．．．．．+．．．．．．．．．．。。．．．．．．．．．．．．。。．．．．．。．．．．．．。。28Letterofcommitment．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．29Authorizationstatement．．．．．．．．．．．．．．．．．．．．

7、．．．．．．．．．．．．．．．．．．．．．．．．．．．．，．．．．．．．．30万方数据中文摘要图的限制连通性问题一直是图论的一个核心课题．由于限制连通度能度量网络的可靠性和容错性，伴随着互连网络的快速发展，近年来对图的限制连通性进行了广泛研究．设G=(VE)是有限简单无向图，其中V=v(G)和E=E(G)分别是G的顶点集和边集．设S是连通图G的一个边割，若G—s的每个连通分支都至少有k个点，则称s是G的一个k一限制边割．称G中所含边数最少的k．限制边割为A％一割．记G的k一限制边连通度札=扎(G)为

8、k一割所含的边数．定义&(G)=mMl[X，-】I：X∈y(G)，IXI=k，G陋】是连通子图)，若沁(G)=靠(G)，则称G是k一最优图．在本文中，我们主要研究几类图限制边连通度的一些问题．本文共分三章：第一章，介绍了文章所涉及的一些概念、术语和符号．第二章，给出了A5一最优图的一个充分条件．主要结果如下：设G是一个∥≥17，6≥【差j一4且A5(G)≤矗(G)的A5一连通图，若(i)G中每个导出六圈以及任意由一条边相连的两个三角形的粘合图中都存在非粘合点u满足d(