5-连通图和7-连通图的可收缩边的分布

《5-连通图和7-连通图的可收缩边的分布》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据山东大学硕士学位论文ChineseAbstract⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯¨⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·IEnglishAbstract．．⋯。。⋯⋯．．“⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IINotations⋯。⋯⋯．．．．．．．．。⋯⋯⋯⋯⋯⋯⋯⋯——⋯⋯⋯⋯⋯⋯⋯⋯。⋯⋯⋯⋯⋯⋯⋯-⋯⋯⋯．一VChapter1Introduction,——⋯”n．————⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一·1§1．1GraphTheoryOverview⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1§1．2BasicConcepts⋯⋯⋯⋯

2、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．2§1．3SomeKnownResults⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3Chapter2TheContractibleEdg翻m。TheS-connectedGraphs⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4§2．1TheContractibleEdgesinTheLongestCircleof5-connectedGraphs⋯⋯⋯⋯⋯4§2．2TheContractibleEdgesinTheSpanningTreeof5-connectedGraphs⋯⋯⋯⋯⋯．8Chapte

3、r3TheContractibleEdgesinThe7-connectedGraphs⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··'1§3．1TheContractibleEdgesinTheLongestCircleof7-cormectedGraphs⋯⋯⋯⋯．．12§3．2TheContractibleEdgesinThespanningTreeof7-comlectedGraphs⋯⋯⋯⋯⋯17§3．3TheContractibleEdgesinThePerfectMatchingof7-connectedGraphs⋯⋯⋯．．17Chapter4TheContractibleEdg●

4、：sinThek-connectedGraphs⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·25Refel'tllCes⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。．．．⋯⋯⋯⋯⋯⋯⋯．．．．．⋯．．⋯⋯⋯⋯27ResearchandPublishedP囊peI譬⋯⋯⋯⋯⋯⋯⋯⋯··⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一··30II万方数据山东大学硕士学位论文5一连通图和卜连通图的可收缩边的分布王振刚山东大学数学学院运筹学与控制论山东济南250100中文摘要图的连通性是图论非常重要的概念之一，图的许多性质和图的连通性有着密切的关系。在图论的研究方法中，我们常常运用一些图的特性的运算，用一些

5、简单的连通图构造出复杂的连通图满足要求的性质。基于此，图的可收缩边运算成为研究复杂连通图的有力工具之一。本文选择连通图的可收缩边作为研究的对象，考虑5一连通图和7一连通图的可收缩边在不同的特定子图一一最长圈、生成树和完美匹配上的分布情况，并得到相应的结果。对于5～连通图，本文首先对5一连通图最长圈上可收缩边的分布的已有成果进行了改进，并首次提出5一连通图生成村上可收缩边的分布情况，得出的主要结论有：定理2．1-3设G是5一连通图，且G中不存在2一断片。尸：z=‘艺⋯艺=少是g的一条最长∽力一路。如果路尸上任一硕点‘都满足以下条件之一，那么尸上至少有两条可收缩边：(1)吹‘)≥6

6、；(2)识‘)=5，则【垠乃】中无3一图包含它。定理2．2．1设G是5一连通图，且G中不存在2一断片，Ⅳ是G的一棵生成树。如果Ⅳ上的任一顶点z均满足以下条件之一，则生成树Ⅳ上至少有一条可收缩边：(1)放t)≥6；万方数据山东大学硕士学位论文(2)破‘)=5，则【以仞】中无3一圈包含它。对于7一连通图，本文仍然采用树形结构理论进行分类讨论，考虑了7一连通图的可收缩边在最长圈、生成树以及完美匹配上的分布情况，得到的主要结论有：定理3．1．5设G是7一连通图，且g的任意断片的阶都大于3。若f：z=而艺⋯‘=少是G的任意最长圈，则f至少包含三条可收缩边。定理3．2．1设G是7一连通图，

7、Ⅳ是G的一棵生成树。如果Gff意一个断片的阶都大于3，那么生成树何上至少包含两条可收缩边。定理3．3．7设G是7一连通图且Iel>15，并且肜是G的一个完美匹配，如果肜上的任意一条边均不在三角形上，那么肜上至少包含两条可收缩边。定理3．3．8设G是7一连通图且lGl>15、∥是g的一个完美匹配，如果图6的任意一个断片的阶都大于3，那么肜上至少包含两条可收缩边。关键词：连通图可收缩边最长圈生成树完美匹配II万方数据山东大学硕士学位论文in-I-he钆onnectedand7吒onnectedG