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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：1247338