6连通图圈和树上的可去边

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

1、山东大学硕士学位论文CONTENTSChineseAbstract．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．IIIEnglishAbstract⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯VNotations⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．VIIChapter1Introduction．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．151．1Researchbackground⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．151．2BasicDefinitionsandNotations51．3St

2、ructureContent⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．9Chapter2RemovableEdgesofCyclesin6-ConnectedGraphs1152．1BasicDefinitionsandPriorhlowledge⋯⋯⋯．⋯⋯⋯⋯⋯．1l§2．2RemovableEdgesofCyclesin6-ConnectedGraphs⋯⋯⋯⋯．12Chapter3RemovableEdgesofSpanningTreesin6-ConnectedGraphs．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．

3、．．．．．．．．．．．．]19§3．1RemovableEdgesofSpanningTreesin6-ConnectedGraphs⋯．19§3．2RemovableEdgesofHamiltonianCyclesin6-ConnectedGraphs．．⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．．．⋯．．．．⋯．．．．．⋯⋯⋯⋯⋯．23References．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．：：《【Acknowledgements⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯27一II—山东大学硕士学位论文6连通图中圈和树

4、上的可去边王莎莎(山东大学数学学院，济南，250100)(指导老师：吴吉昌)摘要图的连通性是图的最基本的性质之一，同时也是图论中的重要研究课题。除了具备较高的理论价值，图的连通性与网络模型以及组合优化等学科课题也有着密切的联系，加之如今计算机和网络技术发展迅速，使得连通图的研究也具有一定的应用价值。探讨连通图的结构特征，寻找连通图的构造方法一直是连通图研究的重要课题。随着数学归纳法在图论中的广泛应用，采用递归的方法，利用连通图阶数的”约简”来对其进行研究日益得到重视，即保持图的某种性质，并使图的阶数或边数减少的一系列运算的综合。在这种背景下，图的可收缩边和可去边被

5、定义和广泛研究。本文以连通图中的可去边作为研究对象，以期能够对进一步了解连通图的结构及其构造方法做出贡献。本文主要研究6连通图中可去边的性质及其在圈和生成树中的分布情况。下面简单介绍一下本文的主要结果。首先我们给出可去边的定义：设图G为6连通图，e=xy是图G的一条边。对图G进行以下运算：(1)从图G中删去边e=xy，得到图G—e。(2)若存在点u∈x，y)，使得u在图G—e中是个5度点，则删掉点u，并将点乱的5个邻点两两连结为砥。(3)若经过(1)(2)运算后的图出现重边，则删除重边以单边代替，使之成为简单图。我们将经过(1)(2)(3)运算得到的图记为Gee。

6、如果Gee仍旧是6连通图，那么边e称为可去边；否则称为可不去边。山东大学硕士学位论文图G的所有可去边的集合记为玩(G)，所有不可去边的集合记为风(G)。本文研究了6连通图中可去边的性质及其在圈上的分布情况，得出下面的结论：结论1图G为IG}≥1l的6连通图，且d(G)≥7，则G的任意一个圈中至少有两条可去边。对于6连通图中可去边在生成树和哈密顿圈上的分布情况，我们得到下面两条结论：结论2图G为IGI≥11的6连通图，且d(G)≥7，则G的任意生成树中至少含两条可去边。结论3图G为IGI≥11的6连通哈密顿图，且6(G)≥7，则G的任意哈密顿圈中至少含三条可去边。关

7、键词：连通图；可去边；圈：生成树一Ⅳ一Removableedgesofcyclesandtreesin6-connectedgraphsShashaWang(Schoolofmathematics，ShandongUniversity，Jinan，250100)(Prosicor：JichangWu)ABSTRACTTheconnectivityisoneofthemostimportantpropertiesofgraphs，whichisalsoanimportantresearchsubject．Besidesofhightheoreticalvalue，C

8、on—ne