發(fā)布時(shí)間：2024-12-11 02:30

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

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

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖２．１：運(yùn)用配對(duì)模型的方法探索鄰點(diǎn)??

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

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

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

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

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

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

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

本文編號(hào)：4016038