故障超立方體類網(wǎng)絡(luò)的極大連通分支

翟登鑫, 阿依古麗·馬木提

(1. 喀什大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 新疆 喀什 844000; 2. 新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 新疆 烏魯木齊 830046)

1 引言及預(yù)備知識

互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)通常由一個連通圖G=(V,E)來表示,其中頂點表示處理器,邊表示通信鏈路.傳統(tǒng)上衡量網(wǎng)絡(luò)可靠性和容錯性的經(jīng)典參數(shù)是連通度和邊連通度.若F?V(G),圖G中刪去F中的所有點后,使得G-F是不連通或者是平凡的,則稱F是圖G的點割.類似地,若S?E(G),圖G中刪去S中的所有邊后,使得G-S是不連通或者是平凡的,則稱S是圖G的邊割.圖G的連通度用κ(G)表示,則κ(G)=min{|F|:F是G的點割}.圖G的邊連通度用λ(G)表示,則λ(G)=min{|S|:S是G的邊割}.然而這2個參數(shù)存在本質(zhì)的缺點,理想狀態(tài)下與圖G的一個頂點相鄰的所有頂點(或邊)不可能同時失效,但這在實際網(wǎng)絡(luò)應(yīng)用中幾乎是不可能的.由于幾乎所有同一處理器的相鄰處理器或同一處理器的所有鏈路都有可能同時失效,為了彌補這個缺點,可以通過對G-F的組件增加一些條件或限制來推廣經(jīng)典連通性的概念,其中F表示有故障的點(或邊).

無向圖G=(V,E)由點集V和邊集E組成,其中V是有限集,E是V中任意2個不同元素的無序?qū)?gòu)成的集合.如果uv∈E,那么u和v兩點是相鄰接的,并且u和v是uv邊的端點.令v是G中的點,點v的鄰集N(v)是與v相鄰接的所有點構(gòu)成的集合,且|N(v)|被稱為點v的度數(shù),記作degG(v)或者簡記為deg(v).圖G中的一些點子集或邊子集,記作F,符號G-F表示從G中刪除F的元素所得到的子圖.令mc(G)為圖G中一個極大連通分支的最大階.圖G的點子集F,令N(F)={u∈V(G)-F:u是與F中的點相鄰接的點}.點子集V′?V,在子圖H(H?G)中的V′的鄰集,被定義為

Vaidya等[1]提出了一類超立方體類網(wǎng)絡(luò),稱為HL-圖(或BC圖),它用以下完美匹配運算“⊕”遞歸定義:HL0={K1},

i={0,1}, n≥1.

顯然,HL1={K2},HL2={C4},HL3={Q3,G(8,4)},其中,C4是四圈,Q3是3維超立方體,且G(8,4)是一個遞歸循環(huán)圖[2],見圖1.

圖 1 HL3

HL-圖類不僅有小直徑,而且有一些優(yōu)良的特性,如正則性、連通性和哈密爾頓性.文獻[3]發(fā)現(xiàn),對HLn中任意滿足條件|F|≤2n-3(n≥2)的點集F,HLn-F包含一個連通分支,其階數(shù)至少為|V(HLn)|-|F|-1.同時,對HLn中任意滿足條件|F|≤3n-6(n≥5)的點集F,HLn-F包含一個連通分支,其階數(shù)至少為|V(HLn)|-|F|-2.但實際上,HLn中可能有更多故障點.因此,研究HLn中有大量故障點的最大連通分支的最大階具有重要意義.

引理 1[1,4]設(shè)HLn是n維超立方體類網(wǎng)絡(luò),則下面4個性質(zhì)成立:

1) |V(HLn)|=2n;

2) |E(HLn)|=n·2n-1;

3)HLn是n-正則的;

4)κ(HLn)=n.

引理 2[5]設(shè)n和k都是正整數(shù),1≤k≤n+1.若F是HLn中點子集,|F|=k,則

此外,F是由HLn中一個點v和它的k-1個鄰點組成的點子集,則

引理 3[6]設(shè)n、k、x、z都是正整數(shù),1≤k≤n-1,1≤x≤k-1,x+1≤z≤x+(k-1)，若

2k(n+1)-k(k+1)≥-z2+

(2x+2n-1)z+(4-2x2),

則z≤k-1.

定理 1[2]若HLn中任意點子集F,|F|≤2n-3,n≥2,則

mc(HLn-F)≥|V(HLn)|-|F|-1.

此外,HLn中存在|F|=2n-2的點子集F,使得

mc(HLn-F)≤|V(HLn)|-|F|-2.

定理 2[2]若HLn中任意點子集F,|F|≤3n-6,n≥5,則

mc(HLn-F)≥|V(HLn)|-|F|-.

此外,HLn中存在|F|=3n-5的點子集F,使得

mc(HLn-F)≤|V(HLn)|-|F|-3.

2 主要結(jié)果

引理 4設(shè)n是整數(shù),n≥5,x是實數(shù),則

x2-(2n+5)x+(2n+1+4)>0.

證明令△為一元二次方程:x2-(2n+5)x+(2n+1+4)=0的判別式,則

△=(2n+5)2-4(2n+1+4)=

(4n2+20n+9)-2n+3.

用歸納法可以證明：當(dāng)n≥5時，2n+3>4n2+20n+9.因此

△=(2n+5)2-4(2n+1+4)=

(4n2+20n+9)-2n+3<0.

因此,一元二次方程無實根,圖像全都在x軸上方,結(jié)論成立.

mc(HLn-F)≥|V(HLn)|-|F|-(k-1).

證明令S是HLn中一個點子集,其由一個點v和它的k-1個鄰點組成.根據(jù)引理2可知

不失一般性,假設(shè)F=N(S).顯然,

mc(HLn-N(S))=

mc(HLn-F)=|V(HLn)|-|F|-k,

即第二部分成立.

下面用歸納法對第一部分進行討論.

mc(HL4-F)≥|V(HL4)|-5-1.

mc(HL5-F)≥|V(HL5)|-6-2.

假設(shè)對n成立,其中n≥4.下面證明對n+1也成立.

情形 11≤k≤n-2.下面分3種子情形進行討論.

mc(HLn+1-F)≥|V(HLn+1)|-|F|-|T|≥

|V(HLn+1)|-|F|-(k-1).

其中0≤p≤r-1,0≤q≤r-1.

根據(jù)引理4可知

因此,

|F|+(p+q),

及

|V(C0)|=2n-|F0|-

令

進一步,令x=|T0|,y=|T1|,z=x+y,則0≤x≤k-1,0≤y≤k-1,及

mc(HLn+1-F)=|V(C)|=

|V(HLn+1)|-|F|-(x+y).

此時,x=0或y=0.接下來假設(shè)x≥1且y≥1.

N*(T0)?F0,N*(T1)?F1.

由此可知

|F0|+|F1|≥|N*(T0)|+|N*(T1)|.

由上述條件及引理2可知

把y=z-x代入上式,化簡得

2k(n+1)-k(k+1)≥

-z2+(2x+2n-1)z+(4-2x2),

其中,1≤x≤k-1,x+1≤z≤x+(k-1)≤x+(n-2).

由上式和引理3可知,z≤k-1及

mc(HLn+1-F)≥|V(HLn+1)|-|F|-|T|≥

|V(HLn+1)|-|F|-(k-1).

情形 2k=n-1,則

下面分4種子情形進行討論.

1) |F1|≤n-2,則|T|≤n-2,因此

mc(HLn+1-F)≥|V(HLn+1)|-

|F|-|T|≥|V(HLn+1)|-|F|-(n-2);

2)T∩F0≠?,則

mc(HLn+1-F)≥|V(HLn+1)|-

|F|-|T|+1≥|V(HLn+1)|-|F|-(n-2);

mc(HLn+1-F)≥|V(HLn+1)|-

|F|-|T|+1≥|V(HLn+1)|-|F|-(n-2);

令N*(T)=N(T)-F1.由假設(shè)可知,N*(T)?F0.因此

這與引理2的

相矛盾.

此時,下面的討論與情形1.3類似.

因此第一部分成立.

mc(HLn-F)≤|V(HLn)|-|F|-(n-2).

為了能夠使得對k=n-1也有類似定理3的結(jié)論,可以通過把定理3中F的取值減少1來得到.

mc(HLn-F)≥|V(HLn)|-|F|-

(k-1)=|V(HLn)|-|F|-(n-3).

mc(HLn-F)≥|V(HLn)|-|F|-(n-2);