兩類網(wǎng)絡(luò)的偶泛圈性和路覆蓋.pdf

1、互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是一個(gè)圖，由含圈拓?fù)浣Y(jié)構(gòu)的圖設(shè)計(jì)出來(lái)的網(wǎng)絡(luò)通訊成本低，應(yīng)用范圍廣，因此圈嵌入一直是圖論和計(jì)算機(jī)領(lǐng)域研究的熱點(diǎn).泛圈性是圈嵌入的延伸，研究從圍長(zhǎng)到頂點(diǎn)個(gè)數(shù)任意長(zhǎng)度的圈嵌入.實(shí)際中網(wǎng)絡(luò)的頂點(diǎn)和鏈接都可能發(fā)生故障，因此容錯(cuò)泛圈性的研究具有極大實(shí)際意義.不相交路是指頂點(diǎn)不相交的路，圖的不相交路覆蓋要求不相交路包含圖中的所有點(diǎn).對(duì)應(yīng)到網(wǎng)絡(luò)上意味著網(wǎng)絡(luò)中所有頂點(diǎn)都可以參與并行路的數(shù)據(jù)路由.不相交路覆蓋的研究有利于網(wǎng)絡(luò)資源的優(yōu)化利用

2、，能夠應(yīng)用在編碼優(yōu)化、數(shù)據(jù)庫(kù)設(shè)計(jì)等領(lǐng)域.
　　n-維超立方體Qn是并行處理和并行計(jì)算系統(tǒng)的首選結(jié)構(gòu)，隨著信息科技的發(fā)展，人們對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的要求越來(lái)越高，許多超立方體的變形網(wǎng)絡(luò)如平衡超立方體、折疊超立方體等相繼被提出，它們具有許多優(yōu)于超立方體網(wǎng)絡(luò)的性質(zhì).
　　本文中結(jié)合數(shù)學(xué)歸納推理和分類討論的方法，對(duì)超立方體和平衡超立方體分別進(jìn)行邊容錯(cuò)偶泛圈性和不相交路覆蓋的研究.論文組織結(jié)構(gòu)如下:
　　第一章緒論中主要介紹了論文中用到

3、的圖論基本概念以及圖的不相交路覆蓋、容錯(cuò)圈嵌入研究的相關(guān)背景知識(shí)和研究現(xiàn)狀.
　　第二章中詳細(xì)介紹了論文中主要研究的兩個(gè)網(wǎng)絡(luò):超立方體和平衡超立方體，分別給出了定義、相關(guān)概念以及與本論文相關(guān)的性質(zhì)結(jié)論.
　　第三章中證明了超立方體Qn的容錯(cuò)偶泛圈性.設(shè)F是超立方體Qn(n≥6)的一個(gè)錯(cuò)誤邊集且|F|≤3n-7，如果滿足(1)Qn中每個(gè)點(diǎn)至少關(guān)聯(lián)兩條好邊和(2)Qn-F中既無(wú)f4-圈，也無(wú)f6-圈，則Qn中存在長(zhǎng)度為e的偶圈，

4、其中e是介于4到2n的任意偶數(shù).
　　第四章中證明了平衡超立方體BHn的配對(duì)的3-不相交路覆蓋，證明當(dāng)n≥3時(shí)，設(shè)源點(diǎn)集S(∈)B和匯點(diǎn)集T(∈)W，則BHn中存在以S∪T為端點(diǎn)集的3-不相交路覆蓋，其中B和W是BHn中黑點(diǎn)集和白點(diǎn)集.這一結(jié)論推廣了Cheng等在[Applied Mathematics and Computation，2014，242:127-142]中給出的BHn中的配對(duì)的2-不相交路覆蓋的結(jié)果.
　　第