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

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

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

3、有泛圈性可以度量該網(wǎng)絡(luò)是否可以嵌入任意長度的圈.泛連通性是泛圈性的深化.如果一個網(wǎng)絡(luò)是泛連通的，則一定是泛圈的.
　　本文主要研究幾個著名網(wǎng)絡(luò)的容錯性和泛連通性，全文共分四章.
　　第一章介紹了本文用到的一些圖與網(wǎng)絡(luò)的基本概念，度量互連網(wǎng)絡(luò)的可靠性和容錯性的幾個參數(shù)，泛連通性的定義以及幾個著名的網(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))這個概念.確定了超立方體Qn的t-最小簇度.即：當1≤t≤n+1時，δt(Qn)=tn-2(t-1)-1/2(t-1)

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