折疊交叉立方體的限制連通度

阿斯牙·米吉提

(喀什大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，新疆 喀什 844000)

0 引 言

眾所周知，互聯(lián)網(wǎng)絡(luò)在并行計(jì)算/通信系統(tǒng)中起著重要的作用.在多處理器系統(tǒng)中，處理器通常根據(jù)由圖G=(V，E)表示的某種互連網(wǎng)絡(luò)連接，其中V中的每個(gè)頂點(diǎn)對(duì)應(yīng)于處理器，E中的每條邊對(duì)應(yīng)于通信鏈路.圖的性質(zhì)決定了系統(tǒng)的工作效率.可靠性是選擇或設(shè)計(jì)互連網(wǎng)絡(luò)時(shí)必須考慮的重要度量之一，評(píng)價(jià)互連網(wǎng)絡(luò)可靠性的兩個(gè)重要參數(shù)是點(diǎn)連通度和邊連通度.連通圖G的點(diǎn)連通度κ(G)(邊連通度λ(G))是頂點(diǎn)子集(邊子集)的最小基數(shù)，將其刪除后圖G不連通.然而，這兩個(gè)參數(shù)都有一個(gè)明顯的不足，即它們默認(rèn)地假定一個(gè)頂點(diǎn)附近的所有頂點(diǎn)(或與一個(gè)頂點(diǎn)相關(guān)聯(lián)的所有邊)都可能同時(shí)失效，這在實(shí)際的多處理器系統(tǒng)中幾乎是不可能的.后來(lái)人們發(fā)現(xiàn)僅有點(diǎn)連通度和邊連通度不能夠準(zhǔn)確反映處理器和通訊信道受損時(shí)系統(tǒng)的損壞程度.為此，Harary于1983年首先提出條件連通度的概念[1]，Esfahanian和Hakimi于1988年更進(jìn)一步提出了限制連通度的概念[2].本文中，我們將關(guān)注折疊交叉立方體的2-限制點(diǎn)(邊)連通度.

n-維交叉立方體CQn[3-4]和n-維折疊超立方體FQn[5]被認(rèn)為是計(jì)算機(jī)系統(tǒng)中最通用、最高效的兩種互聯(lián)網(wǎng)絡(luò).2002年，文獻(xiàn)[7]中提出了一種基于n-維交叉立方體和折疊超立方體的互聯(lián)網(wǎng)絡(luò)——折疊交叉立方體(FCQn).FCQn是一種高性能、低成本的構(gòu)架，具有短直徑、短平均節(jié)點(diǎn)間距離和非常低的消息流量密度等吸引人的特性，文獻(xiàn)[6-8]分別研究了FCQn的不同的性質(zhì).設(shè)子集F?V(G)(F?E(G))(如果存在)稱(chēng)為h-限制點(diǎn)割(h-限制邊割)，如果G-F不連通，并且G-F中的每個(gè)連通分支至少有h+1個(gè)頂點(diǎn)，其中最小的h-限制點(diǎn)割(h-限制邊割)的基數(shù)稱(chēng)為圖G的h-限制連通度(h-限制邊連通度)，記為κh(G)(λh(G)).近幾年，對(duì)限制連通性的研究有著極為豐富的研究?jī)?nèi)容，并得到了一些漂亮的結(jié)果[9-11].本文中，我們確定了n-維折疊交叉立方體FCQn的2-限制(邊)連通度，證明了κ2(FCQn)=3n-1(n≥8)以及λ2(FCQn)=3n-2(n≥7).

1 定義及引理

定義1設(shè)x和y是兩個(gè)2長(zhǎng)的二元字符串，如果(x，y)∈{(00，01)，(10，11)，(01，11)，(11，01)}，則稱(chēng)x和y為相關(guān)對(duì)，并記為x～y.

n-維超立方體Qn的頂點(diǎn)集是由2n個(gè)n長(zhǎng)的二元字符串組成的，其中任意兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們的漢明距離等于1.n-維交叉立方體CQn(n≥2)是一無(wú)向圖，它的頂點(diǎn)集和Qn的頂點(diǎn)集一樣，兩個(gè)頂點(diǎn)x=xnxn-1…x2x1和y=ynyn-1…y2y1相鄰當(dāng)且僅當(dāng)存在j(1≤j≤n)使：

(a)xn…xj+1=yn…yj+1；

(b)xj≠yj；

(c)xj-1=yj-1，如果j是偶數(shù)；

(d)x2ix2i-1～y2iy2i-1，i=1，2，…，「(1/2)j?-1.

圖1 3-維交叉立方體CQ3和FCQ3Fig.1 3 dimensional crossed cube CQ3 and FCQ3

引理1[12]CQn是n-正則的，有2n個(gè)頂點(diǎn)，(n+1)2n-1條邊.

引理2[13]κ(CQn)=λ(CQn)=n.

引理3[14]κ1(CQn)=λ1(CQn)=2n-2.

引理4[8]κ(FCQn)=n+1.

引理5[15]對(duì)n≥2及任意u∈V(CQn)，CQn-NCQn[u]是連通的.

引理6[15]FCQn(n≥4)不含三角形.

引理7[12]對(duì)互異的兩點(diǎn)u，v∈V(FCQn)，|NFCQn(u)∩NFCQn(v)|≤2(n≥4).

2 主要結(jié)果

定理1對(duì)于n≥7，κ2(FCQn)≤3n-2.

證明：由引理7可知，當(dāng)n≥4時(shí)，可以在FCQn中選取兩個(gè)不相鄰的點(diǎn)u、w，使得|N(u)∩N(w)|=2.取u、w的一個(gè)公共鄰點(diǎn)v，且令X={u，v，w}，S=NFCQn-X(X)，則由X的選法，得|S|=|NFCQn-X(X)|=3n-2，且S是一點(diǎn)割，其中FCQn-S的一個(gè)分支X具有3個(gè)頂點(diǎn)，令Y=FCQn-S-X，由于|S∪X|=3n+1

κ2(FCQn)≤|S|=3n-2.

證畢.

定理2對(duì)于n≥8，κ2(FCQn)=3n-2.

情形1.R-KR連通.

情形2.R-KR不連通.

令K′R=KR∪{h}，K′L=KL，則|K′R|≤?(3n-3)/2」+1<κ1(R)=2n-4(n≥7)，R-KR-h不含孤立點(diǎn)，說(shuō)明R-KR-h連通.回到情形1，即L-K′L中任意點(diǎn)都與R-K′R連接.根據(jù)假設(shè)知，點(diǎn)h在FCQn-K中存在鄰點(diǎn)，而此鄰點(diǎn)與R-KR-h連接，從而h可通過(guò)某條路與R-KR-h連接.因此FCQn-K連通.綜合情形1與2，得

κ2(FCQn)≥3n-2.

證畢.

定理3對(duì)n≥4，λ2(FCQn)≤3n-1.

若x∈X，則結(jié)論成立.若x∈NFCQn-X(X)，則因dFCQn(x)=n+1，再由引理7可知，|N(x)∩X|≤ 2，因此dFCQn-E(X)(x)≥n+1-2=n-1>2(n≥4)，結(jié)論成立；若x∈VFCQnN[X]，則此時(shí)dFCQn-E(X)(x)=dFCQn(x)=n+1>2，結(jié)論成立，即E(X)是FCQn的一個(gè)2-限制邊割，從而λ2(FCQn)≤|E(X)|≤3n-1(n≥4).證畢.

定理4對(duì)n≥7，λ2(FCQn)=3n-1.

證明：由定理3可知，只需證λ2(FCQn)≥3n-1(n≥7).令K是FCQn的一個(gè)邊集，|K|≤3n-2，且FCQn-K不含任何孤立點(diǎn)和孤立邊.為了證明λ2(FCQn)≥3n-1，只需證FCQn-K是連通的.令FCQn=L⊕R，M是L與R之間補(bǔ)邊與交叉邊的全體.再令K=KL∪KM∪KR，其中KL=K∩L，KM=K∩M，KR=K∩R.因?yàn)镽-KR要么連通，要么不連通，故分兩種情形討論.

情形1R-KR連通.

當(dāng)(NL(x){y})∩(NL(z){y})=?時(shí)，上述路共有3n-7條，且任意兩條路無(wú)重邊.

當(dāng)(NL(x){y})∩(NL(z){y})≠?時(shí)，根據(jù)引理7，存在唯一的一個(gè)頂點(diǎn)a∈(NL(x){y})∩(NL(z){y})，另取R中的點(diǎn)aR與a相連，此時(shí)pi∪pj∪p′∪{aaR}共有3n-7條路，且任意兩條路無(wú)重邊.由|KL|+|KM|+|KR|≤3n-2，以及|KM|≥6知，|KL|+|KM|-6≤3n-8<3n-7，故上述兩種情況下3n-7條路中必有某條路與KL∪KM無(wú)重邊，x通過(guò)此條路與R-KR連接.

情形2R-KR不連通.

因?yàn)閨KL|+|KM|+|KR|≤3n-2，所以|KL|+|KR|≤3n-2-|KM|<3n-2，不妨設(shè)|KR|≤|KL|，則|KR|≤ ?(3n-2)/2<λ1(R)=2n-4(n≥7).由引理3可得，R-KR含孤立點(diǎn)h，所以R中與h相鄰的邊集ER(h)?KR.又因dR(h)=n-1，且|KR|<2n-4，則有|KR|-|ER(h)|≤n-4.對(duì)任意t∈V(R-ER(h)-h)，dR(t)≥n-2>n-4，從而R-KR-h不含孤立點(diǎn)，下證R-KR-h必連通.

用反證法.若它不連通，則連接點(diǎn)h與h在R中的一個(gè)鄰點(diǎn)hN，可以得到一新圖R-KR∪{hhN}，且此圖仍不連通，此圖是由R刪掉2n-6條邊得到，且無(wú)孤立點(diǎn).但另一方面，由引理3知，R-KR∪{hhN}連通，矛盾.因此R-KR-h必連通，且此時(shí)|KR|≥n-1，從而|KL|+|KM|=|K|-|KR|≤2n-1.現(xiàn)只需證任意x∈L-KL，x與R-KR-h連接，而h與L-KL中的某個(gè)點(diǎn)相鄰，h通過(guò)此點(diǎn)連接到R-KR-h.此情形下有三種情形：

情形2.1|KL|≤2n-5.

情形2.22n-4≤|KL|≤2n-3.

情形2.2.2.1xh∈KM.

情形2.2.2.2xh?KM，有以下兩種情形：

情形2.2.2.2.1hhL∈KM.

情形2.2.2.2.2hhL?KM.

情形2.32n-2≤KL≤2n-1.

λ2(FCQn)≥3n-1(n≥7)，

從而定理4成立.證畢.