秦學(xué)姣

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

圖1 G1的構(gòu)造

圖的圖示

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

構(gòu)造如下：

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}。

按照這個(gè)定理的結(jié)論，我們可以得到表1。

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

3 帶有條件邊故障的的強(qiáng)Menger邊連通度

證明：使用數(shù)學(xué)歸納法來(lái)證明。當(dāng)n=2時(shí)，引理結(jié)論顯然成立。假設(shè)引理對(duì)n-1時(shí)結(jié)論成立。下面證明引理對(duì)n結(jié)論成立，這里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的結(jié)果是最優(yōu)的。

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

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

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

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

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

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