本文關(guān)鍵詞：圖的限制邊連通性與哈密爾頓性

  更多相關(guān)文章： 圖 互連網(wǎng)絡(luò) 極大κ限制邊連通圖 超級κ限制邊連通圖 極大κ等周邊連通圖 Hamiltonian圖 κ限制邊連通度 λ_κ-碎片 團 圍長

【摘要】：多處理機系統(tǒng)的互連網(wǎng)絡(luò)拓撲通常以圖為數(shù)學(xué)模型,因此網(wǎng)絡(luò)拓撲的性能可以通過圖的性質(zhì)和參數(shù)來度量.在設(shè)計和選擇多處理機系統(tǒng)的互連網(wǎng)絡(luò)拓撲時,我們要考慮的一個問題是系統(tǒng)的可靠性(容錯性).邊連通度λ(G)是度量網(wǎng)絡(luò)可靠性的一個重要參數(shù).通常,邊連通度A(G)越大,網(wǎng)絡(luò)越可靠.但是,這個參數(shù)有一個明顯的缺陷：它假定系統(tǒng)的任何部分都可能同時損壞,這在實際應(yīng)用中幾乎不可能發(fā)生.為彌補這個缺陷,Fabrega和Fiol提出了k限制邊連通度的概念.對于互連網(wǎng)絡(luò)來說,有一類重要的問題,是在某一個網(wǎng)絡(luò)上模擬另外一個網(wǎng)絡(luò),這個問題被稱為網(wǎng)絡(luò)嵌入問題.圖的嵌入是把客圖映射到主圖.許多應(yīng)用,如建筑仿真,處理器分配,和超大規(guī)模集成電路芯片設(shè)計,可以建模為圖的嵌入.本文主要研究圖的k限制邊連通性和Hamiltonian性.本文共分五章.第一章首先給出本文將用到的圖論方面的術(shù)語和記號,然后綜述圖的k限制邊連通性和Hamiltonian性的應(yīng)用背景和研究進展,最后概述了本文的研究內(nèi)容和獲得的主要結(jié)論.作為邊連通度的推廣,k限制邊連通度是度量圖的連通性的一個重要參數(shù).當(dāng)k=2時,2限制邊連通度通常被稱為限制邊連通度.2012年,Holtkamp等研究了非極大限制邊連通無3-圈圖的λ2-碎片的基數(shù)的下界和非極大k限制邊連通無3-團圖的Ak-碎片的基數(shù)的下界.進一步,給出了極大限制邊連通無3-圈圖和極大k限制邊連通無3-團圖的充分條件.第二章主要研究無(p+1)-團圖和圍長為g的圖的極大k限制邊連通性.我們首先給出了一個非極大k限制邊連通且無(p+1)-團圖的λk-碎片的基數(shù)的下界.其次,我們給出了一個圍長為9的非極大k限制邊連通圖的λk-碎片的基數(shù)的下界.最后,一些極大k限制邊連通圖的充分條件被給出.近年來,圖的極大限制邊連通性和極大3限制邊連通性得到了廣泛的研究.但是關(guān)于更一般的k限制邊連通性研究略少.這需要被推廣到更一般的情形.2004年,Hell-wig和Volkmann證明了：如果λ'-連通圖G中所有不相鄰頂點u,v都滿足N(u)∩N(v)|≥2,且G中每個三角形T中都存在一點u使得d(v)≥[(v(G))/2]+1,那么G是極大限制邊連通的.第三章主要研究了圖的極大k限制邊連通性和超級k限制邊連通性.我們首先給出了一個圖是極大k限制邊連通的充分條件,這個結(jié)果推廣了上面的結(jié)論.其次,我們證明了如果G中任意一對不相鄰頂點都有d(u)+d(v)≥v(G)+2k-4且G不屬于一類特殊圖,那么G是極大k限制邊連通的.最后,我們給出了一個圖是超級k限制邊連通的度條件.k等周邊連通度是一個與k限制邊連通度密切相關(guān)的概念.它也是度量網(wǎng)絡(luò)可靠性的一個重要的參數(shù).2009年,Wang等人證明了一個階至少為2k的圖G,如果G中任意一對不相鄰頂點u,v都滿足W(u)∩N(u)|≥2k-1,那么G是極大k等周邊連通的.第四章主要研究極大k等周邊連通圖的鄰域交條件.我們首先給出了一個在k等周邊連通圖中,由γk-碎片生成的子圖中存在(k-1)-路的充分條件.其次,我們給出了極大等周邊圖的一個鄰域交條件,這個是上面結(jié)果的一個改進.最后研究了直徑為2的圖的極大k等周邊連通性.一個圖G中的Hamiltonian圈是指經(jīng)過G中每個頂點恰好一次的圈Hamiltonian圈的嵌入是圖論中的一個熱點問題.第五章主要研究直徑為2的圖中的Hamiltonian圈.首先,我們給出了相關(guān)的概念和結(jié)果.然后,我們證明了如果對于階至少是3的圖G中任意一對不相鄰頂點都有N(u)∩N(u)|≥[v/2]-1,且G不屬于一類特殊圖,那么G是一個Hamiltonian圖.
【學(xué)位授予單位】：山西大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【相似文獻】

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

1 霍美霞;高敬振;;圖的四階邊連通度的存在性[J];科學(xué)技術(shù)與工程;2007年14期

2 周艷;武燕;;關(guān)于金字塔網(wǎng)限制邊連通度的研究[J];西南大學(xué)學(xué)報(自然科學(xué)版);2007年08期

3 楊超;徐俊明;;強乘積圖的連通度和邊連通度(英文)[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2008年05期

4 蔡俊青;高敬振;;k階限制邊連通度最優(yōu)的一個充分條件[J];科學(xué)技術(shù)與工程;2008年13期

5 趙元慶;金顯華;;星網(wǎng)的4-限制邊連通度[J];計算機工程與應(yīng)用;2012年13期

6 李國君;一類特殊圖的連通度與邊連通度之間的關(guān)系[J];煙臺師院學(xué)報(自然科學(xué)版);1987年02期

7 張勝貴，，王自果;系統(tǒng)的核度與邊連通度[J];系統(tǒng)工程與電子技術(shù);1995年06期

8 江秉華;陳金陽;王志平;;圖的平均邊連通度[J];北華大學(xué)學(xué)報(自然科學(xué)版);2013年06期

9 王應(yīng)前,李喬;圖的限制性邊連通度等于其最小邊度的一個充分條件[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯(中文版);2001年03期

10 王銘,李喬;關(guān)于圖的超常邊連通度和等周邊連通度的等值性[J];上海交通大學(xué)學(xué)報;2002年06期

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

1 呂敏;徐俊明;范英梅;;無向de Bruijn圖的超邊連通度(英文)[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（下卷）[C];2004年

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

1 張磊;圖的限制邊連通性與哈密爾頓性[D];山西大學(xué);2015年

2 尚莉;圖的高階限制邊連通度[D];蘭州大學(xué);2008年

3 李峰偉;網(wǎng)絡(luò)的若干穩(wěn)定性參數(shù)的研究[D];南開大學(xué);2006年

4 祁忠斌;曲面Fullerene圖的環(huán)邊連通度、共振性及哈密爾頓性[D];蘭州大學(xué);2008年

5 王建偉;容錯網(wǎng)絡(luò)中若干問題研究[D];中國科學(xué)技術(shù)大學(xué);2010年

6 李向軍;某些網(wǎng)絡(luò)容錯性研究[D];中國科學(xué)技術(shù)大學(xué);2013年

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

1 郭利濤;圖的3-限制性邊連通度和3-限制性連通度[D];新疆大學(xué);2008年

2 桑鎮(zhèn);關(guān)于k階限制邊連通度若干問題的研究[D];山東師范大學(xué);2009年

3 陳亮;高階限制邊連通度的最優(yōu)性和超級性[D];山東師范大學(xué);2009年

4 張鳳娟;k階限制邊連通度的最優(yōu)性和超級性[D];山東師范大學(xué);2009年

5 蔡俊青;k-限制邊連通度的存在性與上界[D];山東師范大學(xué);2009年

6 楊瑩瑩;圖的k階限制邊連通度的若干性質(zhì)[D];山東師范大學(xué);2010年

7 李鑫;關(guān)于圖的k-限制邊連通度的最優(yōu)性和超級性[D];山東師范大學(xué);2010年

8 孟祥軍;圖的低階限制邊連通度的研究[D];山東師范大學(xué);2010年

9 馬玉;圖的k-限制邊連通度性質(zhì)的研究[D];山東師范大學(xué);2011年

10 周宏強;圖的k-限制邊連通度的最優(yōu)性和超級性[D];山東師范大學(xué);2011年

本文編號：1247338