發(fā)布時(shí)間：2017-07-20 17:26

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

  更多相關(guān)文章： 連通圖 可收縮邊 最長(zhǎng)圈 生成樹(shù) 完美匹配

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

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

【相似文獻(xiàn)】

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

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

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

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

4 趙克文,曾克揚(yáng);哈密爾頓連通圖的一點(diǎn)注記[J];工程數(shù)學(xué)學(xué)報(bào);2003年02期

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

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

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

8 林福財(cái);關(guān)于4連通圖的容錯(cuò)直徑和寬直徑[J];漳州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2005年01期

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

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

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

1 張薇;張立輝;乞建勛;李星梅;蘇志雄;;帶正權(quán)的無(wú)向連通圖中最短路問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

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

1 羅朝陽(yáng);圖的點(diǎn)度與距離型拓?fù)渲笜?biāo)參數(shù)及其應(yīng)用[D];山東大學(xué);2015年

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

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

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

5 陳曉東;無(wú)爪圖及其擴(kuò)展圖的Hamilton性[D];大連理工大學(xué);2012年

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

7 蔡建生;圖的因子和分?jǐn)?shù)因子[D];山東大學(xué);2007年

8 梁浩;圖的拉普拉斯矩陣和臨界群[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

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

10 Alaa Amer Najim;關(guān)于圖的邊添加和邊減少問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2006年

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

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

2 余世群;一類極大臨界h連通圖的結(jié)構(gòu)[D];廣西師范大學(xué);2003年

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

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

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

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

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

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

9 吳敏如;圖中過(guò)給定點(diǎn)集的圈結(jié)構(gòu)[D];華中師范大學(xué);2015年

10 常曉玲;4-連通圖中最長(zhǎng)圈上弦的存在性與可去邊的關(guān)系[D];山東大學(xué);2015年

，

本文編號(hào)：569204