本文關鍵詞：兩類網絡的偶泛圈性和路覆蓋

  更多相關文章： 超立方體 平衡超立方體 不相交路覆蓋 容錯性 偶泛圈性

【摘要】：互連網絡的拓撲結構是一個圖,由含圈拓撲結構的圖設計出來的網絡通訊成本低,應用范圍廣,因此圈嵌入一直是圖論和計算機領域研究的熱點.泛圈性是圈嵌入的延伸,研究從圍長到頂點個數(shù)任意長度的圈嵌入.實際中網絡的頂點和鏈接都可能發(fā)生故障,因此容錯泛圈性的研究具有極大實際意義.不相交路是指頂點不相交的路,圖的不相交路覆蓋要求不相交路包含圖中的所有點.對應到網絡上意味著網絡中所有頂點都可以參與并行路的數(shù)據(jù)路由.不相交路覆蓋的研究有利于網絡資源的優(yōu)化利用,能夠應用在編碼優(yōu)化、數(shù)據(jù)庫設計等領域.n-維超立方體Qn是并行處理和并行計算系統(tǒng)的首選結構,隨著信息科技的發(fā)展,人們對于網絡結構的要求越來越高,許多超立方體的變形網絡如平衡超立方體、折疊超立方體等相繼被提出,它們具有許多優(yōu)于超立方體網絡的性質.本文中結合數(shù)學歸納推理和分類討論的方法,對超立方體和平衡超立方體分別進行邊容錯偶泛圈性和不相交路覆蓋的研究.論文組織結構如下：第一章緒論中主要介紹了論文中用到的圖論基本概念以及圖的不相交路覆蓋、容錯圈嵌入研究的相關背景知識和研究現(xiàn)狀.第二章中詳細介紹了論文中主要研究的兩個網絡：超立方體和平衡超立方體,分別給出了定義、相關概念以及與本論文相關的性質結論.第三章中證明了超立方體Qn的容錯偶泛圈性.設F是超立方體Qn(n≥6)的一個錯誤邊集且|F|≤3n-7,如果滿足(1)Qn中每個點至少關聯(lián)兩條好邊和(2)Qn-F中既無f4-圈,也無f6-圈,則Qn中存在長度為l的偶圈,其中l(wèi)是介于4到2n的任意偶數(shù).第四章中證明了平衡超立方體BHn的配對的3-不相交路覆蓋,證明當n≥3時,設源點集S(?)B和匯點集T(?)W,則BHn中存在以S∪T為端點集的3-不相交路覆蓋,其中B和W是BHn中黑點集和白點集.這一結論推廣了Cheng等在[Applied Mathematics and Computation,2014,242:127-142]中給出的BHn中的配對的2-不相交路覆蓋的結果.第五章結束語對本文進行了總結,并給出了進一步的研究方向.
【關鍵詞】：超立方體 平衡超立方體 不相交路覆蓋 容錯性 偶泛圈性
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 致謝5-6
• 中文摘要6-7
• ABSTRACT7-10
• 第一章 緒論10-16
• 1 研究背景和意義10-11
• 2 基本概念和預備知識11-13
• 3 研究現(xiàn)狀13-16
• 第二章 超立方體及平衡超立方體定義及性質16-22
• 1 超立方體16-19
• 2 平衡超立方體19-22
• 第三章 超立方體的邊容錯偶泛圈性22-39
• 1 預備引理證明22-23
• 2 超立方體中存在3n-7條錯誤邊時的邊容錯偶泛圈性23-39
• 第四章 平衡超立方體的不相交路覆蓋39-50
• 1 預備引理證明39-40
• 2 平衡超立方體中配對的3-不相交路覆蓋40-50
• 第五章 結束語50-51
• 參考文獻51-55
• 附錄55-63
• 作者簡歷63-65
• 學位論文數(shù)據(jù)集65

【相似文獻】

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

1 馬美杰,徐俊明;交叉超立方體網絡的邊泛圈性(英文)[J];中國科學技術大學學報;2005年03期

2 徐露霞;陳芳躍;;n維超立方體中隱含低維超方體的計數(shù)問題[J];杭州電子科技大學學報;2012年02期

3 范漪涵;劉紅美;劉敏;;故障折疊超立方體中的路和圈(英文)[J];數(shù)學雜志;2013年03期

4 侯晶;張先迪;;廣義超立方體網絡的容錯性和通信延遲[J];電子科技大學學報;2006年02期

5 高志軍;蔡穎;杜杰;溫宇鵬;;超立方體三次冪的可區(qū)別數(shù)研究[J];大連海事大學學報;2006年02期

6 公維鳳;劉紅美;宦紅倫;謝煒;;廣義超立方體網絡中一類容錯路由選擇[J];數(shù)學的實踐與認識;2006年09期

7 高志軍;李懿;張紹兵;;超立方體的邊可區(qū)別數(shù)[J];黑龍江科技學院學報;2007年05期

8 高志軍;李懿;何鳴;;維數(shù)不超過7的超立方體三次冪的可區(qū)別數(shù)[J];黑龍江科技學院學報;2008年01期

9 杜正中;經};馬美杰;徐俊明;;容錯超立方體網絡的圈嵌入(英文)[J];中國科學技術大學學報;2008年09期

10 佘衛(wèi)強;方來金;;邊故障超立方體中兩條無故障點不交路[J];漳州師范學院學報(自然科學版);2009年01期

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

1 馬美杰;徐俊明;杜正中;;超立方體網絡的邊容錯泛連通性與折疊超立方體網絡的邊容錯邊泛圈性(英文)[A];中國運籌學會第七屆學術交流會論文集（下卷）[C];2004年

2 許艷;;超立方體切面中的樣條方法[A];第六屆全國幾何設計與計算學術會議論文集[C];2013年

3 司沛;楊小帆;劉懷義;王燦;孫麗萍;;局部扭曲立方體的邊泛圈性[A];2008年計算機應用技術交流會論文集[C];2008年

4 公維鳳;王傳會;劉紅美;;廣義超立方體的容錯路由選擇[A];第八屆中國青年運籌信息管理學者大會論文集[C];2006年

5 張軍英;許進;保錚;;一類離散Hopfield網的特征分析(Ⅱ)——穩(wěn)定吸引狀態(tài)的結構[A];1999年中國神經網絡與信號處理學術會議論文集[C];1999年

6 張軍英;許進;保錚;;一類離散Hopfield網的特征分析(Ⅰ)—穩(wěn)定吸引狀態(tài)[A];1999年中國神經網絡與信號處理學術會議論文集[C];1999年

7 張修梅;;關于超立方體與M銉bius立方體的連接[A];第八屆中國青年運籌信息管理學者大會論文集[C];2006年

中國重要報紙全文數(shù)據(jù)庫 前2條

1 高博;超立方體可充當納米計算機結構[N];科技日報;2008年

2 馮衛(wèi)東;越小越精[N];科技日報;2008年

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

1 陳浩;復雜結構拉丁超立方體設計的構造[D];南開大學;2013年

2 王海亮;超立方體網絡的容錯泛連通性[D];中國科學技術大學;2009年

3 杜正中;容錯網絡的路和圈研究[D];中國科學技術大學;2006年

4 王國軍;具有大量錯誤結點的超立方體網絡容錯模型和容錯路由算法研究[D];中南大學;2002年

5 王洪偉;超立方體網絡中多播路由優(yōu)化策略研究[D];哈爾濱工業(yè)大學;2013年

6 經衿;某些容錯網絡的嵌入研究[D];中國科學技術大學;2009年

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

1 黃瑩;交換超立方體網絡的故障診斷策略研究[D];廣西大學;2015年

2 劉秀麗;類超立方體網絡的g好鄰條件診斷度[D];太原科技大學;2015年

3 羅歡;三類網絡在PMC模型下的悲觀診斷[D];北京交通大學;2016年

4 郭美榮;兩類網絡的偶泛圈性和路覆蓋[D];北京交通大學;2016年

5 文盼;限制超立方體類網絡的不相交的路覆蓋[D];北京交通大學;2016年

6 馬良;超立方體網絡上與距離相關的容錯性研究[D];蘇州大學;2016年

7 喬宏偉;超立方體的生成連通性質以及對換網絡的可系性[D];新疆大學;2016年

8 高志軍;超立方體可區(qū)別數(shù)的研究[D];大連海事大學;2006年

9 吳智霞;折疊超立方體的容錯泛圈性[D];北京交通大學;2012年

10 張茹;平衡超立方體的限制邊連通性[D];北京交通大學;2012年

，

本文編號：785107