本文關鍵詞：5-連通圖和7-連通圖的可收縮邊的分布

  更多相關文章： 連通圖 可收縮邊 最長圈 生成樹 完美匹配

【摘要】：圖的連通性是圖論非常重要的概念之一,圖的許多性質和圖的連通性有著密切的關系。在圖論的研究方法中,我們常常運用一些圖的特性的運算,用一些簡單的連通圖構造出復雜的連通圖滿足要求的性質�；诖�,圖的可收縮邊運算成為研究復雜連通圖的有力工具之一。本文選擇連通圖的可收縮邊作為研究的對象,考慮5-連通圖和7-連通圖的可收縮邊在不同的特定子圖——最長圈、生成樹和完美匹配上的分布情況,并得到相應的結果。對于5-連通圖,本文首先對5-連通圖最長圈上可收縮邊的分布的已有成果進行了改進,并首次提出5-連通圖生成樹上可收縮邊的分布情況,得出的主要結論有：定理2.1.3設G是5-連通圖,且G中不存在2-斷片。P：x=x1x2…xn=少是G的一條最長(x,y)-路。如果路P上任一頂點xi都滿足以下條件之一,那么P上至少有兩條可收縮邊：(1)d(xi)≥6；(2)d(xi)=5,則[V(P)]中無3-圈包含它。定理2.2.1設G是5-連通圖,且G中不存在2-斷片,H是G的一棵生成樹。如果H上的任一頂點均滿足以下條件之一,則生成樹H上至少有一條可收縮邊：(1)d(xi)≥6；(2)d(ci)=5,則[V(H)]中無3-圈包含它。對于7-連通圖,本文仍然采用樹形結構理論進行分類討論,考慮了7-連通圖的可收縮邊在最長圈、生成樹以及完美匹配上的分布情況,得到的主要結論有：定理3.1.5設G是7-連通圖,且G的任意斷片的階都大于3。若C：x=x1x2…xn=少是G的任意最長圈,則C至少包含三條可收縮邊。定理3.2.1設G是7-連通圖,H是G的一棵生成樹。如果口任意一個斷片的階都大于3,那么生成樹H上至少包含兩條可收縮邊。定理3.3.7設G是7-連通圖且|G|15,并且M是G的一個完美匹配,如果M上的任意一條邊均不在三角形上,那么M上至少包含兩條可收縮邊。定理3.3.8設G是7-連通圖且|G|15,M是G的一個完美匹配,如果圖G的任意一個斷片的階都大于3,那么M上至少包含兩條可收縮邊。
【關鍵詞】：連通圖 可收縮邊 最長圈 生成樹 完美匹配
【學位授予單位】：山東大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要6-8
• ABSTRACT8-10
• 符號說明10-11
• 第一章 緒論11-14
• §1.1 圖論概述11-12
• §1.2 基本概念12-13
• §1.3 成果綜述13-14
• 第二章 5-連通圖的可收縮邊的分布14-21
• §2.1 5-連通圖最長圈的可收縮邊的分布14-18
• §2.2 5-連通圖生成樹的可收縮邊的分布18-21
• 第三章 7-連通圖的可收縮邊的分布21-35
• §3.1 7-連通圖最長圈的可收縮邊的分布22-27
• §3.2 7-連通圖生成樹的可收縮邊的分布27
• §3.3 7-連通圖完美匹配的可收縮邊的分布27-35
• 第四章 k-連通圖的可收縮邊的分布35-37
• 參考文獻37-39
• 致謝39-40
• 攻讀碩士學位期間發(fā)表的學術論文40-41
• 附件41

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 謝果;判定k-點連通圖與k-邊連通圖極小性的定理[J];四川師范大學學報(自然科學版);2000年05期

2 余世群;一類極大臨界h連通圖的性質[J];湖北民族學院學報(自然科學版);2002年04期

3 齊登記,余世群;收縮臨界6-連通圖中的6度點[J];湖北民族學院學報(自然科學版);2002年04期

4 趙克文,曾克揚;哈密爾頓連通圖的一點注記[J];工程數(shù)學學報;2003年02期

5 趙克文;哈密爾頓連通圖與鄰域并條件[J];信息工程大學學報;2003年02期

6 余世群;一類極大臨界2連通圖的結構[J];湖北民族學院學報(自然科學版);2004年04期

7 陳儀朝,蘇健基;恰含5條非基本邊的極小3連通圖[J];廣西師范大學學報(自然科學版);2004年03期

8 林福財;關于4連通圖的容錯直徑和寬直徑[J];漳州師范學院學報(自然科學版);2005年01期

9 余世群;;一類極大臨界4連通圖的結構[J];湖北民族學院學報(自然科學版);2006年02期

10 劉育興;蘇健基;;恰有k條非基本邊的極小3連通圖[J];數(shù)學研究與評論;2006年04期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 張薇;張立輝;乞建勛;李星梅;蘇志雄;;帶正權的無向連通圖中最短路問題研究[A];中國運籌學會第九屆學術交流會論文集[C];2008年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 羅朝陽;圖的點度與距離型拓撲指標參數(shù)及其應用[D];山東大學;2015年

2 吳亞平;k-連通圖中最長圈及余直徑研究[D];華中師范大學;2011年

3 康海燕;連通圖中可去邊和圈的研究[D];山東大學;2010年

4 劉素娟;2-（邊-）連通圖的彩虹連通數(shù)[D];南開大學;2013年

5 陳曉東;無爪圖及其擴展圖的Hamilton性[D];大連理工大學;2012年

6 侯新民;網(wǎng)絡（圖）廣義直徑的研究[D];大連理工大學;2002年

7 蔡建生;圖的因子和分數(shù)因子[D];山東大學;2007年

8 梁浩;圖的拉普拉斯矩陣和臨界群[D];中國科學技術大學;2009年

9 洪振木;某些網(wǎng)絡可靠性和有效性研究[D];中國科學技術大學;2014年

10 Alaa Amer Najim;關于圖的邊添加和邊減少問題研究[D];中國科學技術大學;2006年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 齊恩鳳;k-連通圖的可收縮邊和可收縮圈[D];廣西師范大學;2006年

2 余世群;一類極大臨界h連通圖的結構[D];廣西師范大學;2003年

3 覃城阜;收縮臨界5-連通圖的性質[D];廣西師范大學;2004年

4 楊迎球;k連通圖中的k可收縮邊[D];廣西師范大學;2007年

5 張志芳;6連通圖中的可收縮邊[D];河南師范大學;2011年

6 畢振明;恰含6條非基本邊的極小3連通圖[D];山東大學;2012年

7 王雪;7-連通圖最長圈上的可收縮邊及3-連通圖可收縮非邊的分布[D];山東大學;2013年

8 劉秀松;幾類圖的全局強迫數(shù)和完全強迫數(shù)[D];蘭州大學;2015年

9 吳敏如;圖中過給定點集的圈結構[D];華中師范大學;2015年

10 常曉玲;4-連通圖中最長圈上弦的存在性與可去邊的關系[D];山東大學;2015年

，

本文編號：569204