條件故障下3-元n-立方體的容錯分析

秦學姣

(新疆醫(yī)科大學 厚博學院，新疆 克拉瑪依 834000)

在設計一個互連網絡時，容錯性是一個基本原則，邊連通性是衡量互連網絡容錯性的一個重要指標。圖G的邊連通度，記作λ(G)，定義為使G不連通時需刪除的最小邊數(shù)。然而，邊連通度往往低估了多處理系統(tǒng)的容錯能力。在很多情況下，當故障邊數(shù)大于邊連通度時，一個具有故障邊的網絡仍可能是連通的，或者存在較大的連通分支[1-3]。因此，互連網絡的容錯性與帶有故障邊的網絡的較大連通分支的頂點數(shù)密切相關。

假設F是圖G的一故障邊集，G-F是從G中刪除F得到的圖,u和v是圖G-F中的兩個頂點，我們關心的是G-F中u和v之間的邊不相交無故障路徑的數(shù)目。我們將此問題考慮為邊故障條件下的Menger定理[4]。近年來，學者們對互連網絡的Menger特性進行了大量的研究[5-7]。特別地，Qiao等[6]研究了條件故障下的超立方體和折疊超立方體的強Menger邊連通性。

k-元n-立方體是一類重要的互連網絡。一方面，其包括了傳統(tǒng)的互連網絡作為其子類，如環(huán)(1-元n-立方體)、超立方體(2-元n-立方體)和環(huán)面(k-元 2-立方體)。另一方面，目前已經建立了多個大型并行分布式計算系統(tǒng)，如Gray T3D、J-machine、iWarp和Blue Gene，都是基于k-元n-立方體的拓撲結構。近年來，k-元n-立方體的許多拓撲性質得到了廣泛的研究[8-13]。例如，Li等[9]考慮了路限制條件下將路和圈嵌入到3-元n-立方體中的問題；Yuan等[11]研究了3-元n-立方體網絡的g-好鄰點條件可診斷性。目前，有關條件故障下k-元n-立方體的強Menger性的研究較少。本文研究了具有條件邊故障的3-元n-立方體網絡的較大連通分支和強Menger邊連通性。

1 預備知識

定義1[5]連通圖G稱為條件邊故障下的f-強Menger連通度，是指在F?E(G),|F|≤f和δ(G-F)≥2條件下，G-F中任意一對頂點u和v之間存在min{degG-F(u),degG-F(v)}條邊不交的無故障路。

2 帶有故障邊的3-元n-立方體的較大連通分支

取(t+1)組3-元子立方體，其頂點集互不相交。用Qi代表第i組3-元子立方體，這里0≤i≤t。而每一個Qi包含xi個3-元yi-維子立方體，記做Qi,1,…，Qi,xi。

Qi,ji表示第ji個3-元yi-維子立方體，這里0≤i≤t,1≤ji≤xi≤2。G1可以用一種遞歸的方式得到。給定Q0,j0，其包含x0個3-元y0-維子立方體，在不產生歧義的時候，我們也使用U1U2…Uy0-1Uy0(j0-1)00…00來代表Q0,j0，3-元yi-維子立方體Qi,ji(i>0)是指Qi-1,xi-1把第(yi-1+1)位的(ji-1-1)改為xi-1，把Qi-1,xi-1的第(yi+1)位坐標改為(ji-1)而獲得。除了第(yi-1+1)位坐標外，令第(yi+2)位坐標到第yi-1位坐標都是0。G1的構造如圖1所示。

圖1 G1的構造

圖的圖示

為了方便理解這個構造的方法，下面舉一個具體的例子(圖2)：

構造如下：

Q0,j0,j0=1:U1U20；

Q1,j1,j1=1:U101；

Q2,j2,j2=1,2:011,111。

且V(G1)={000,100,200,010,110,210,020,120,220}∪{001,101,201}∪{011}∪{111}={000,100,200,010,110,210,020,120,220,001,101,201,011,111}。

按照這個定理的結論，我們可以得到表1。

表1 帶有故障邊的的較大連通分支

3 帶有條件邊故障的的強Menger邊連通度

證明：使用數(shù)學歸納法來證明。當n=2時，引理結論顯然成立。假設引理對n-1時結論成立。下面證明引理對n結論成立，這里n≥3。

情況1 |S2|≤4n-7

情形1.1 |S0|≤|S1|≤|S2|≤2n-3

情形1.2 |S0|≤|S1|≤2n-3且2n-2≤|S2|≤4n-7

情形1.3 |S0|≤2n-3且2n-2≤|S1|≤|S2|≤4n-7

情況2 |S0|≤|S1|≤4n-7且4n-6≤|S2|≤4n-3

綜上所述，引理得證。

注解3.2 引理3.1的結果是最優(yōu)的。

證明方法與引理3.1類似，故略。

注解3.4 引理3.3的結果是最優(yōu)的。

情況1 |V(H)|=3n-1

情況2 |V(H)|=3n-2

下面，證明這個結論是最優(yōu)的。

圖3 定理3.5的圖示Fig.3 Illustration for the Theorem 3.5