本文關(guān)鍵詞：圖的割、割基相關(guān)理論研究

  更多相關(guān)文章： 割空間 割 基本割 割基 最大割基

【摘要】：本文主要研究連通圖的割空間相關(guān)理論和相關(guān)的若干性質(zhì),這些內(nèi)容在圖論研究領(lǐng)域中占重要地位。但是,與連通圖的圈空間相關(guān)理論相比,連通圖的割空間相關(guān)理論的發(fā)展并不是很成熟,而且對其研究得也比較少。本文將應(yīng)用連通圖的割空間與圈空間相互正交的關(guān)系,解決部分割空間的問題。本文也嘗試將圈空間部分現(xiàn)有的研究方法應(yīng)用到割空間。本文第三章主要研究關(guān)于連通圖的割中的問題,首先證明了割成為極小割的充要條件；然后,證明了極小割與極小割的對稱差可以得到一個新的割；證明了最小割與最小割的集合并運算能得到一個最小割；最后,證明了,階無向連通圖G(V,E)中割的數(shù)目最多為2n-1-1個；n階有向連通圖G(V,E)中不同割的數(shù)目為2n-2。本文第四章證明了n階連通圖G(V,E)割空間中割基相關(guān)性質(zhì)。首先證明了割基的非唯一性,具體內(nèi)容是舉出割空間中兩個具體割基并給予證明；對比n階連通圖G(V,E)圈空間中的基本圈,相應(yīng)的給出n階連通圖G(V,E)的割空間中基本割概念,并證明了割空間中一個割基可以由n-1個線性無關(guān)的基本割構(gòu)成。其次,證明了割空間中最大割基的唯一性。對于這塊內(nèi)容考慮到一個最大割基可以反映出一個連通圖的最大割信息,由此得到結(jié)論：許多的連通圖中最大割的信息包含在最大割基中。根據(jù)前期得到的關(guān)于一個基變換的Hall型定理得到以下成果(1)給出了證明一個割基是最大割基的充要條件；(2)證明了最大割與最大割基的關(guān)系；(3)證明了兩個最大割基保持權(quán)重一致。最后,本文給出了在無向連通圖中最大割基的權(quán)重取值范圍為在有向連通圖中最大有向割的權(quán)重下界為最后,本文給出割的應(yīng)用,主要思想是嘗試先對平面圖的對偶圖中割的數(shù)目進(jìn)行估計再反過來估計平面圖中圈的數(shù)目,力爭優(yōu)化已有關(guān)于圈、最短圈數(shù)目的上限值。一方面,先考慮n階無向連通圖,首先證明了n階無向連通圖G(V,E)(平面圖)中的圈與其連通對偶圖G’(V’,E')中的割一一對應(yīng)。在此基礎(chǔ)上得到一個推論：若n階無向連通圖G’(V',E')中割數(shù)目最多為2n-1-1個,那么它的連通對偶圖G(V,E)中的圈數(shù)目也不超過2n-1-1個。其次,簡述了幾種比較簡便并且高效求最小割的方法,其時間復(fù)雜度比目前求最短圈的時間復(fù)雜度低。另一方面,針對n階有向連通圖G(V,E),弓用了“TP”對偶圖的定義,使得n階有向連通圖G(V,E)中的圈與其連通對偶圖G’(V’,E’)中的割一一對應(yīng)結(jié)論成立。這樣,對于n階有向連通圖G(V,E)也可以采用先求割數(shù)目進(jìn)而得到圈數(shù)目的方法。
【關(guān)鍵詞】：割空間 割 基本割 割基 最大割基
【學(xué)位授予單位】：中央民族大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-5
• 英文摘要5-10
• 第一章 引言10-13
• 第二章 預(yù)備知識13-16
• 第三章 連通圖中割的若干性質(zhì)16-22
• 第一節(jié) 割與極小割的關(guān)系16-20
• 第二節(jié) 割的計數(shù)問題20-22
• 第四章 割空間中割基的相關(guān)性質(zhì)22-31
• 第一節(jié) 割基的非唯一性證明22-27
• 第二節(jié) 最大割基的唯一性證明27-31
• 第五章 割的應(yīng)用31-36
• 第一節(jié) 應(yīng)用割理論求解無向圈的計數(shù)問題31-34
• 第二節(jié) 應(yīng)用割理論求解有向圈的計數(shù)問題34-36
• 第六章 總結(jié)展望36-37
• 參考文獻(xiàn)37-40
• 致謝40-41
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄41

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前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-連通圖最長圈上的可收縮邊及3-連通圖可收縮非邊的分布[D];山東大學(xué);2013年

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

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

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

，

本文編號：616216