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

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

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

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

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

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

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

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

圖 1 HL3

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

引理 1[1,4]設(shè)HLn是n維超立方體類網(wǎng)絡(luò),則下面4個(gè)性質(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中點(diǎn)子集,|F|=k,則

此外,F是由HLn中一個(gè)點(diǎn)v和它的k-1個(gè)鄰點(diǎn)組成的點(diǎn)子集,則

引理 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中任意點(diǎn)子集F,|F|≤2n-3,n≥2,則

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

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

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

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

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

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

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

2 主要結(jié)果

引理 4設(shè)n是整數(shù),n≥5,x是實(shí)數(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時(shí)，2n+3>4n2+20n+9.因此

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

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

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

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

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

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

mc(HLn-N(S))=

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

即第二部分成立.

下面用歸納法對(duì)第一部分進(jìn)行討論.

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

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

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

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

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

令

進(jìn)一步,令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).

此時(shí),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代入上式,化簡(jiǎn)得

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種子情形進(jìn)行討論.

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的

相矛盾.

此時(shí),下面的討論與情形1.3類似.

因此第一部分成立.

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

為了能夠使得對(duì)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);