互連網(wǎng)絡(luò)的容錯(cuò)性和泛連通性.pdf

1、互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是計(jì)算機(jī)系統(tǒng)或通信系統(tǒng)中元件之間的連接方式，它是決定該系統(tǒng)性能的重要因素之一.一個(gè)互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以被模擬成一個(gè)無向圖G=(V,E).這時(shí)，圖G中的頂點(diǎn)代表網(wǎng)絡(luò)中的元件，G中的邊表示元件之間的通信連線.網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定著該網(wǎng)絡(luò)的性能.一個(gè)圖的連通度和邊連通度是衡量該互連網(wǎng)絡(luò)可靠性和容錯(cuò)性的重要參數(shù).而且圖的連通度和邊連通度越大，它所模擬的互連網(wǎng)絡(luò)的可靠性越高.但是，這兩個(gè)參數(shù)有明顯的缺陷.因?yàn)樗鼈兗僭O(shè)與同一個(gè)頂點(diǎn)相

2、鄰的所有頂點(diǎn)或所有邊可能同時(shí)故障.然而，這在網(wǎng)絡(luò)的實(shí)際應(yīng)用中幾乎是不可能的.
　　為了正確地度量網(wǎng)絡(luò)的容錯(cuò)性，除了連通度和邊連通度，更多新的參數(shù)被提出，例如：額外連通度和額外邊連通度.對于一個(gè)非負(fù)整數(shù)g，圖G的g-額外連通度κg(G)(g-額外邊連通度λg(G))是最小點(diǎn)數(shù)(邊數(shù))，這個(gè)數(shù)目的點(diǎn)集(邊集)從G中移走會(huì)導(dǎo)致剩下的圖不連通且每個(gè)連通分支至少有g(shù)+1個(gè)頂點(diǎn).
　　可嵌入性是度量網(wǎng)絡(luò)優(yōu)劣的一個(gè)重要性能，一個(gè)網(wǎng)絡(luò)是否具

3、有泛圈性可以度量該網(wǎng)絡(luò)是否可以嵌入任意長度的圈.泛連通性是泛圈性的深化.如果一個(gè)網(wǎng)絡(luò)是泛連通的，則一定是泛圈的.
　　本文主要研究幾個(gè)著名網(wǎng)絡(luò)的容錯(cuò)性和泛連通性，全文共分四章.
　　第一章介紹了本文用到的一些圖與網(wǎng)絡(luò)的基本概念，度量互連網(wǎng)絡(luò)的可靠性和容錯(cuò)性的幾個(gè)參數(shù)，泛連通性的定義以及幾個(gè)著名的網(wǎng)絡(luò)的定義.
　　第二章研究kn-hypermesh網(wǎng)絡(luò)和n-維spinedcube網(wǎng)絡(luò)的額外連通度和額外邊連通度.首先證明了

4、kn-hypermesh網(wǎng)絡(luò)的1-額外連通度和2-額外連通度分別為κ1(HMn,k)=2n(k-1)-k(n≥3,k≥3)和κ2(HMn,k)=3n(k-1)-2k-1(n≥4,k≥4).然后證明了SQn的1-額外連通度和1-額外邊連通度均為2n-2(n≥3).
　　第三章通過引入圖的t-最小簇度(記為δt(G))這個(gè)概念.確定了超立方體Qn的t-最小簇度.即：當(dāng)1≤t≤n+1時(shí)，δt(Qn)=tn-2(t-1)-1/2(t-1)

5、(t-2).然后又討論了故障立方體的結(jié)構(gòu)，并證明了，在一個(gè)n-維立方體Qn中，當(dāng)0≤t≤n-3時(shí)，對于一個(gè)故障集F且|F|<δt+1(Qn)，Qn-F有一個(gè)大連通分支且剩下所有小連通分支總共至多有t個(gè)頂點(diǎn).
　　第四章研究了kn-hypermesh網(wǎng)絡(luò)HMn,k的泛連通性.證明了HMn,k是泛連通的.即對任意兩個(gè)不同頂點(diǎn)x,y∈V(HMn,k)，它們之間存在從d(x,y)到l≤kn-1的每個(gè)長度的(x,y)-路，其中d(x,y)是