隨著數(shù)字通訊技術和計算機技術的快速發(fā)展,大量的信息在計算機網(wǎng)絡中傳輸.計算機的編碼方式和信號在信道上傳輸?shù)目煽啃�、有效性、適應性、經(jīng)濟性等性能成為計算機網(wǎng)絡研究中的重要課題.本論文研究與網(wǎng)絡的可靠性和效率相關的特殊圖類的結構.論文的第一部分研究了扭曲超立方體的容錯直徑和寬直徑.容錯直徑和寬直徑是衡量網(wǎng)絡的可靠性、有效性、經(jīng)濟性等性能的兩個參數(shù).設l是一個正整數(shù),且圖G是l-連通的.圖G的l-容錯直徑,記為dlf(G),是滿足下列條件的最小整數(shù)dd:對于任意的X(?)V(G),若|X| ≤ l-1,則G-X的直徑不超過d;圖G的l-寬直徑,記為dl(G),是滿足下列條件的最小整數(shù)d:對于任意的頂點x,y ∈ V(G),G中包含l條內(nèi)部點不交的且長度不超過d的路.在限定頂點數(shù)和頂點最大度的條件下,超立方體和扭曲超立方體的直徑比較小且具有良好的擴展性.因此,超立方體和扭曲超立方體在網(wǎng)絡設計中被廣泛應用.本文引進隨機扭曲超立方體(RQn)的概念,研究了三類特殊扭曲超立方體Zn,k、Hn以及RQn的容錯直徑和寬直徑,得到以下結果:(1)對于任意的n-維扭曲超立方體Gn∈ Qn,有dnf(Gn)≤3...

【文章頁數(shù)】：118 頁

【學位級別】：博士

【部分圖文】：

圖２．１：運用配對模型的方法探索鄰點??

這里將會多次運用這個思想．例如，考慮生成的一個過程．首先幵始于２４個頂??點，其中每一個頂點包含４個點．現(xiàn)在圖還沒有一條邊，目標是探索對于圖中任意一個??頂點ｕ包含４個點ａ?：６，ｃ，ｄ的匹配（邊）的生成情況（見圖２．１）．點ａ在１－型匹配中只能??匹配點ｅ．因為一個點必須匹配相....

圖２．２：情況１．頂點Ｕ和Ｗ分別在圖的兩邊且是相鄰的．??

第二章扭曲超立方體的結構研究成后就結束了這條路的尋找．因此，增加一個常數(shù)３長度上，這個并不會產(chǎn)生一個線性的項．??點ｕ和ｗ分別在圖么的兩邊且是相鄰的．??且Ｉ；?ｅ氐所以它們只能通過ｎ－型匹配相鄰？此時只需要尋找另外的７１－１條路．令叫，．．．，￣＿１是頂隊是頂點ｒ在Ｂ中的鄰點．....

圖２．３：情況２．頂點ｕ和ｔ；分別在圖（〇７，的兩邊，它們不相鄰且沒有公共

上面一樣首先在４這一邊令＝?｛埤，…，ｗｎ—２，?＜—丨｝且Ｘ?＝?｛％?？／？＿；�。�，其次在這一??邊，令［／?＝?｛ｌ；〗，．．．?且Ｘ?＝?｛％叫－１｝，分別應用推論２．４．１即可？見圖２．４．??情況４．頂點ｕ和ｔ；在圖的同一邊．??情況４．１?Ｍ和Ｕ是相鄰的．??因為....

圖２．４：情況３．頂點ｗ和ｔ；分別在圖么的兩邊，且它們不相鄰但有一個公共的鄰點．??

?那么以概率為１—〇（２－２＂）可以得到兩兩互相不交的集合??然后繼續(xù)前面的方法來暴露ｎ－型匹配（即由Ａ到Ｓ的匹配），當??１?Ｓ?Ｓ?ｎ?—?３時．有％到Ｖ／的邊；［／？＿２到Ｖ的邊；以及到Ｗ的邊．見圖２．５．??Ｉ?＂＂＂＂＂＂??圖２．５：情況４．１?ｕ和ｕ是相鄰的．??情....

本文編號：4016038