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

秦學姣

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

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

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

k-元n-立方體是一類重要的互連網絡。一方面，其包括了傳統的互連網絡作為其子類，如環(1-元n-立方體)、超立方體(2-元n-立方體)和環面(k-元 2-立方體)。另一方面，目前已經建立了多個大型并行分布式計算系統，如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邊連通度

證明：使用數學歸納法來證明。當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的結果是最優的。

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

注解3.4 引理3.3的結果是最優的。

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

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

下面，證明這個結論是最優的。

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