郭慧媚, 阿依古麗·馬木提

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 新疆 烏魯木齊 830046)

現(xiàn)今,人們構(gòu)建了各種各樣的互聯(lián)網(wǎng)絡(luò).通過互聯(lián)網(wǎng)絡(luò)交換信息的具有高性能的多處理器系統(tǒng)需隨著實際生活的需要而被開發(fā).一般來說,一個互聯(lián)網(wǎng)絡(luò)可以被視為一個無向圖G=(V,E),V中的每一個頂點就代表一個處理器,E中的每一條邊代表通信線路.連通度κ和邊連通度λ通常是用來衡量網(wǎng)絡(luò)可靠性和容錯性的參數(shù)[1-2].然而,這兩個參數(shù)只適用于一些互聯(lián)網(wǎng)絡(luò).實際運用中的互聯(lián)網(wǎng)絡(luò)往往比較復(fù)雜,這兩種測量的參數(shù)都有一些缺陷,因為與某一個出錯的處理器鄰接的所有處理器或與某一個出錯的處理器關(guān)聯(lián)的所有通信線路并不總是同時失去運行能力.為了克服這一缺陷并獲得更準(zhǔn)確的測量,推廣經(jīng)典的連通度的概念很有必要.Harary 是第一個對連接組件增加限制的人,他定義了條件連通度[3].

n-維的超立方體Qn是經(jīng)典的互聯(lián)網(wǎng)絡(luò).這個網(wǎng)絡(luò)的許多性質(zhì)已經(jīng)被證明.當(dāng)n≥3時,κ1(Qn)=2n-2;當(dāng)n≥5時,κ2(Qn)=3n-5[5].當(dāng)n≥3時,λ1(Qn)=2n-2;當(dāng)n≥4時,λ2(Qn)=3n-4[6].折疊超立方體FQn是Qn的變體,首先由El-Amawy等[7]提出.文獻(xiàn)[6,8]證明了當(dāng)n≥4時,κ1(FQn)=2n；當(dāng)n≥8時,κ2(FQn)=3n-2；當(dāng)n≥5 時,λ2(FQn)=3n-1.Xu等[9]證明了當(dāng)n≥2時,λ1(FQn)=2n.在1992 年,Kemal[10]定義了n-維交叉超立方體.Chen等[11]證明了當(dāng)n≥4時,κ1(CQn)=λ1(CQn)=2n-2.Yang等[12]證明了當(dāng)n≥4時,λ2(CQn)=3n-4;當(dāng)n≥5時,κ2(CQn)=3n-5.在CQn和FQn的基礎(chǔ)上,Zhang[13]在2002年定義了折疊交叉超立方體FCQn.比起前面的幾種互聯(lián)網(wǎng)絡(luò),折疊交叉超立方體具有更多良好的性質(zhì),比如：更短的直徑、更短的平均節(jié)間距離,以及非常低的信息流量密度[14].最近,Cai等[15]證明了當(dāng)n≥4時,κ1(FCQn)=λ1(FCQn)=2n.

本文主要證明了當(dāng)n≥8時,κ2(FCQn)=3n-2;當(dāng)n≥5時,λ2(FCQn)=3n-1.為了方便證明,在n+1維上討論.

1 預(yù)備知識

本節(jié)介紹一些定義、引理以及標(biāo)號.

其中V(S)表示S中的頂點集,E(S) 表示S中的邊集.圖G的圍長g(G)表示G中的最短圈.本文中所用到的標(biāo)號和定義可以參考文獻(xiàn)[1].

定義 1.1[16]兩個二進(jìn)制字符串u=u1u0和v=v1v0被稱作是配對相關(guān)的,當(dāng)且僅當(dāng)它們滿足

(u,v)∈{(00,00),(01,11),(11,01),(10,10)},

用符號u～v表示；若u和v不配對相關(guān),表示為uv.

n-維交叉超立方體CQn有2n個頂點和n2n-1條邊.關(guān)于CQn的定義如下.

1) 若n是偶數(shù),則un-2=vn-2;

CQn中的任意2個點u=un-1un-2…u0,v=vn-1vn-2…v0是鄰接的當(dāng)且僅當(dāng)存在一個正整數(shù)l,1≤l≤n,使得下列4個條件同時被滿足:

1)iun-2…ul=ivn-2…vl;

2)ul-1≠vl-1;

3) 若l是偶數(shù),ul-2=vl-2;

其中

因此,可以將FCQn表示為

其中

V(FCQ

E(FCQ

FCQ3和FCQ4如圖1所示.

圖 1 FCQ3與FCQ4

引理 1.4[16]κ(CQn)=λ(CQn)=n.

引理 1.5[11]當(dāng)n≥3時,

κ1(CQn)=λ1(CQn)=2n-2.

引理 1.6[6,12]當(dāng)n≥5時,κ2(CQn)= 3n-5;當(dāng)n≥4時,λ2(CQn)= 3n-4.

引理 1.7[17]κ(FCQn)=λ(FCQn)=n+1.

引理 1.8[15]當(dāng)n≥4時,CQn不含三圈.

引理 1.9[15]CQn中的任意2個點u和v最多有2個公共鄰點,即|NCQn(u)∩NCQn(v)|≤2.

引理 1.10[16]CQn中的任意2個點u和v含有2個公共鄰點當(dāng)且僅當(dāng)存在i、j滿足0≤i

證明已知uiui-1∈{00,01,10,11},當(dāng)

綜上討論,引理成立.

引理 1.12[15]FCQn中的任意2個不同的點u和v最多含有2個公共鄰點,即

|NFCQn(u)∩NFCQn(v)|≤2.

引理 1.13[15]當(dāng)n≥4時,FCQn中不含三圈.

引理 1.14FCQn中的任意一個點位于一個四圈中.

當(dāng)i是偶數(shù)時,同樣可以找到一個點v滿足uj=vi,ui=vj,此時有

所以FCQn中的任意一個頂點u位于四圈uuivviu中,引理成立.

證明這個推論可以直接通過引理1.11以及對照表1～3得到,在這里不做過多贅述.

表 1 與u相關(guān)的點

表 2 與uiui-1相關(guān)的二進(jìn)制字符串(I)

表 3 與uiui-1相關(guān)的二進(jìn)制字符串(II)

2 主要結(jié)果

A={ui,(ui)n:i∈{0,1,2，…,n-1}}∩F,

B={(uj)t,((uj)t)n:t∈{0,1,2，…,n-1},t≠j}∩F,

C={(uk)i,((uk)i)n:i∈{0,1,2，…,n-1},i≠j,k},

|C∩F|≤|F-(A∪B∪D)|=
|F|-|A|-|B|-|D|≤n-3.

引理 2.2當(dāng)n≥7時,κ2(FCQn+1)≤3n+1.

證明設(shè)C是FCQn+1中的四圈,P是這個四圈的二長路,顯然|NFCQn+1(P)|=3n+1.接下來,將證明NFCQn+1(P)使FCQn+1不連通,并且FCQn+1-(NFCQn+1(P)∪P)是含有至少3個頂點的連通分支.

并且

2n-6-(3n-5)-3>2n-22(n+1)>4,

|FCQn+1-(NFCQn+1(P)∪P)|≥3.

2n-(2n-1)-2-(n+2)-1>2n-22(n+1)>4,

通過上述分析,可以得到NFCQn+1(P)使FCQn+1不連通,FCQn+1去掉NFCQn+1(P)后剩下的每個連通分支都至少包含3個頂點,即

κ2(FCQn+1)≤3n+1.

引理 2.3當(dāng)n≥7時,κ2(FCQn+1)≥3n+1.

|F′|=|F1|+1<2n-3+1=2n-2=κ1(CQn),

則0≤|Q|≤n-6,而且Q中的頂點可能位于

當(dāng)|F1|=n-6+2+n時,可以得到

|F0|≤3n-|F1|=n+4,

且|H|=n+5.當(dāng)|F1|=n-7+2+n時,可以得到

|F0|≤3n-|F1|=n+5,

因此,當(dāng)|F|≤3n,且FCQn+1-F既不包含孤立點也不包含孤立邊時,FCQn+1-F是連通的.即當(dāng)n≥7時,κ2(FCQn+1)≥3n+1.

定理 2.4當(dāng)n≥7時,κ2(FCQn+1)=3n+1.

引理 2.6當(dāng)n≥4時,λ2(FCQn+1)≤3n+2.

證明在FCQn+1中,設(shè)P是一條二長路,那么

引理 2.7當(dāng)n≥4時,λ2(FCQn+1)≥3n+2.

|F1|<2n-2=λ1(CQn),

則

|B∩F|≤3n+1-n-n-3=n-2.

綜上所述,當(dāng)|F|≤3n+1,FCQn+1-F既不包含孤立點,也不包含孤立邊時,可以得到FCQn+1-F是一個連通分支.即當(dāng)n≥4時,λ2(FCQn+1)≥3n+2.

定理 2.8當(dāng)n≥4時,λ2(FCQn+1)=3n+2.

3 結(jié)論

本文探究了n-維折疊交叉超立方體FCQn的2-額外連通度和2-額外邊連通度.FCQn是具有許多良好性質(zhì)的網(wǎng)絡(luò).證明當(dāng)n≥8時,κ2(FCQn)=3n-2；當(dāng)n≥5時,λ2(FCQn)=3n-1.也就是說,當(dāng)n≥8時,至少要去掉3n-2個頂點,當(dāng)n≥5時,至少要去掉3n-1條邊,使得FCQn不連通,并且剩下的每個連通分支至少有3個頂點.