折疊交叉立方體的1-好鄰診斷度

安婷珠, 蔡學(xué)鵬, 劉夢瑤, 杜濛雨

(新疆農(nóng)業(yè)大學(xué) 數(shù)理學(xué)院,新疆 烏魯木齊 830052)

眾所周知,互連網(wǎng)絡(luò)在平行計(jì)算及通信系統(tǒng)中發(fā)揮著重要作用.一個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在數(shù)學(xué)上通常被抽象地模型化為一個圖G=(V(G),E(G)),其中:V(G)是圖的頂點(diǎn)集,表示網(wǎng)絡(luò)處理器的集合;E(G)是圖G的邊集,表示網(wǎng)絡(luò)的通信鏈路集.

本文中術(shù)語圖與網(wǎng)絡(luò)可以互換使用且所有的圖都認(rèn)為是無向的、簡單的且連通的.

設(shè)G=(V,E)是一個圖.對于圖G的任意非空頂點(diǎn)子集K?V(G),以K為頂點(diǎn)集,以兩端點(diǎn)均在K中的邊的全體為邊集所組成的子圖稱為K在G中的導(dǎo)出子圖,記作G[K].對于圖G中兩個不同的點(diǎn)子集H和K,設(shè)HΔK=(H-K)∪(K-H),NH(K)是在H中且與K中的點(diǎn)相鄰的點(diǎn)的集合. 特殊地,若K={v},可記作NH(v). 設(shè)dG(v)=|NG(v)|是點(diǎn)v在圖G中的度. 如果不產(chǎn)生歧義,可省略下標(biāo),即記為(d(v),N(v)).δ(G)=min{d(v)|v∈V(G)}表示圖G的最小度.對于任意的F?V,若v∈V-F且v在G[V-F]中至少有g(shù)個鄰點(diǎn),則稱F為G的g-好鄰故障集.若G-F不連通且G-F的每個連通分支的最小度為g,則稱F是G的一個g-好鄰割.G的所有g(shù)-好鄰割中基數(shù)最小的g-好鄰割的基數(shù)稱為G的g-好鄰連通度,記作k(g)(G).未說明的圖論符號和術(shù)語可參考文獻(xiàn)[1—2].

連通度和診斷度是度量多處理器系統(tǒng)故障診斷能力的重要參數(shù).為了保證計(jì)算機(jī)系統(tǒng)的可靠性,系統(tǒng)中的故障處理器應(yīng)該被診斷出來并被非故障處理器替換. Preparata等首次提出了系統(tǒng)級故障診斷模型,稱為PMC模型[3],它通過兩個相鄰的處理器之間相互測試完成系統(tǒng)的診斷. Maeng和Malek 提出了MM*模型[4].在該模型下,一個頂點(diǎn)分別給它相鄰的兩個頂點(diǎn)發(fā)出相同的任務(wù),然后比較它們反饋的結(jié)果.傳統(tǒng)的診斷度允許點(diǎn)的鄰點(diǎn)全為故障點(diǎn),但是在大型多處理器系統(tǒng)中這種故障出現(xiàn)的概率極小.因此Lai等提出了網(wǎng)絡(luò)的條件診斷度[5],它限制系統(tǒng)中任意一個處理器至少與一個非故障處理器相鄰. 2012年, Peng等通過在系統(tǒng)中限制每個非故障頂點(diǎn)都至少有g(shù)個非故障鄰點(diǎn),提出網(wǎng)絡(luò)(圖)的g-好鄰診斷度[6]且證明了超立方體在PMC模型下的g-好鄰診斷度是2g(n-g)+2g-1(0≤g≤n-3).2016年,Zhang等在文獻(xiàn)[7]中通過限制G-F(F?V(G))的每個非故障分支中都至少有g(shù)+1個頂點(diǎn),提出了網(wǎng)絡(luò)(圖)g-額外診斷度的概念,并且證明了n-維超立方體Qn在PMC模型下的g-額外診斷度等于n(g+1)-g-0.5g(g-1)(n≥4,0≤g≤n-4).同時,他們還證明了在某些情況下n-維超立方體Qn在MM*模型下的g-額外診斷度等于n(g+1)-g-0.5g(g-1).g-好鄰診斷度和g-額外診斷度比傳統(tǒng)的診斷度診斷互連網(wǎng)絡(luò)(圖)更為精確．

在平行計(jì)算系統(tǒng)中,n-維交叉立方體CQn[8—9]和n-維折疊超立方體FQn[10]是最重要且最流行的兩個互連網(wǎng)絡(luò).基于交叉立方體和折疊超立方體,文獻(xiàn)[11]中提出n-維折疊交叉立方體,記作FCQn.FCQn具有許多重要的特性,如短的直徑、短的平均距離和非常低的消息流量密度. 對于FCQn的詳細(xì)結(jié)果可參考文獻(xiàn)[11—15].

Adhikari等在文獻(xiàn)[15]中證明了FCQn的連通度等于n+1,n≥2.蔡等在文獻(xiàn)[14]中確定了k(1)(FCQn)=2n,n≥4, 馬等在文獻(xiàn)[16]中確定了CQn在PMC模型與MM*下的1-好鄰診斷度分別等于2n-1,n≥4和2n-1,n≥5. 本文將證明FCQn在PMC模型與MM*下的1-好鄰診斷度分別等于2n+1,n≥5和2n+1,n≥6.

1 預(yù)備知識

在MM*模型下,與一個頂點(diǎn)w相鄰的兩個頂點(diǎn)u,v被分配一個相同的任務(wù),把測試結(jié)果反饋給頂點(diǎn)w,再對這兩個頂點(diǎn)反饋的結(jié)果進(jìn)行比較.用(u,v)w表示w比較u,v輸出的結(jié)果,若這兩個結(jié)果是相同的,則(u,v)w=0;否則,(u,v)w=1.稱全部的測試結(jié)果為該系統(tǒng)的比較癥候,記作σ*.假定3個結(jié)點(diǎn)都是非故障的,則測試結(jié)果為0; 若w是非故障的,但u,v至少有一個是故障的,則比較結(jié)果為1;若w是故障的,則測試結(jié)果無論是0或1都是不可靠的.

定義1[17]設(shè)G=(V,E)是一個圖,對于圖G中任意兩個不同的g-好鄰故障集F1和F2,其中|F1|≤t,|F2|≤t,若F1與F2是可區(qū)分的,則G是g-好鄰t-可診斷的.

定義2[17]設(shè)G=(V,E)是一個圖, 使得圖G是g-好鄰t-可診斷的最大值t稱為G的g-好鄰診斷度,記作tg(G).

定義3設(shè)x=x1x0,y=y1y0是兩個二進(jìn)制字符串,若(x,y)∈{(00,00),(10,10),(01,11),(11,01)},則稱x與y是相關(guān)的,記作x～y.

n維交叉立方體CQn的頂點(diǎn)集為V(CQn)={bn-1bn-2…b0|bi∈{0,1},0≤i≤n-1},其遞歸定義如下.

(ⅰ)當(dāng)n是偶數(shù)時,un-2=vn-2;

通過以上定義可得下列推論.

推論1[8]CQn中的兩個頂點(diǎn)u=un-1un-2…u0與v=vn-1vn-2…v0是相鄰的,當(dāng)且僅當(dāng)存在整數(shù)l,1≤l≤n,滿足下列條件:

(ⅰ)un-1…ul=vn-1…vl;

(ⅱ)ul-1≠vl-1;

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

圖1是CQ3和FCQ3的圖.由定義可知,FCQn是有2n個頂點(diǎn)和(n+1)2n-1條邊的(n+1)-正則圖.

圖1 CQ3 和FCQ3

引理1[15]k(FCQn)=n+1,n≥2.

文獻(xiàn)[14]中證明了下面的一些結(jié)論.

引理2[14]設(shè)u和v是CQn中2個不同的頂點(diǎn),則|NCQn(u)∩NCQn(v)|≤2.

引理3[14]FCQn(n≥4)中不含三長圈.

引理4[14]設(shè)u和v是FCQn中兩個不同的頂點(diǎn),則|NFCQn(u)∩NFCQn(v)|≤2.

引理5[14]k(1)(FCQn)=2n,n≥4.

2 主要結(jié)論

2.1 折疊交叉立方體網(wǎng)絡(luò)在PMC模型下的1-好鄰診斷度

定理1[3]一個圖G=(V,E)在PMC模型下是g-好鄰t-可診斷的當(dāng)且僅當(dāng)對于V中任意兩個不同的頂點(diǎn)數(shù)至多為t的g-好鄰故障集F1和F2,存在u∈V-(F1∪F2)和v∈F1ΔF2,使得(u,v)∈E(G)(圖2).

圖2 PMC模型下的可區(qū)分對(F1,F2)

采用反證法證明. 假設(shè)存在兩個不同的1-好鄰故障集F1和F2,其中|Fi|≤2n+1,i=1,2,對任意的u∈V(FCQn-(F1∪F2))和v∈F1ΔF2使得(u,v)?E(FCQn).不失一般性,假設(shè)F2-F1≠?. 考慮下面兩種情形:

情形1V(FCQn)=F1∪F2.

2n=|V(FCQn)|=|F1|+|F2|-

|F1∩F2|≤|F1|+|F2|≤

2n+1+2n+1=4n+2

當(dāng)n≥5時, 上述不等式矛盾.

情形2V(FCQn)≠F1∪F2.

根據(jù)假設(shè)V(FCQn-(F1∪F2))與F1ΔF2之間沒有邊且F1是1-好鄰故障集,可得δ(FCQn-(F1∩F2))≥1和δ(FCQn[F1-F2])≥1.

同理,若F1-F2≠?,則δ(FCQn[F2-F1])≥1,因此,F1∩F2也是1-好鄰故障集且|F1∩F2|≥2. 又因V(FCQn-(F1∪F2))與F1ΔF2之間沒有邊,所以FCQn-F1-F2不連通. 故F1∩F2是FCQn的1-好鄰割.根據(jù)引理5可得|F1∩F2|≥2n. 因此,|F2|=|F2-F1|+|F1∩F2|≥2+2n=2n+2,這與|F2|≤2n+1相矛盾.

結(jié)合引理6和引理7可得下列定理:

2.2 折疊交叉立方體網(wǎng)絡(luò)在MM*模型下的1-好鄰診斷度

定理3[4]一個系統(tǒng)G=(V,E)在MM*模型下是g-好鄰t-可診斷的當(dāng)且僅當(dāng)對V中任意兩個不同的頂點(diǎn)數(shù)至多為t的g-好鄰故障集F1和F2,滿足下列條件之一(圖3):

圖3 在MM*模型下可區(qū)分對(F1,F2)

(ⅰ)存在u,w∈V(G-(F1∪F2))和v∈F1ΔF2滿足(u,w),(v,w)∈E(G);

(ⅱ)存在u,v∈F1-F2和w∈V(G-(F1∪F2))滿足(u,w),(u,v)∈V(G-(F1∪F2));

(ⅲ)存在u,v∈F2-F1和w∈V(G-(F1∪F2))滿足(u,w),(v,w)∈E(G).

引理9設(shè)F1和F2是FCQn(n≥6)中兩個不同的1-好鄰故障集,其中|Fi|≤2n+1,i=1,2,并且F1、F2不滿足定理3中(ⅰ)～(ⅲ), 則FCQn-F1-F2中沒有孤立頂點(diǎn).

證明不失一般性假設(shè)F1-F2≠?.

反證法.假設(shè)FCQn-F1-F2中至少存在一個孤立頂點(diǎn)w. 由于F1是一個1-好鄰故障集,所以至少存在一點(diǎn)u∈F2-F1使得(u,w)∈E(FCQn). 因?yàn)镕1、F2不滿足定理3中(ⅲ),所以至多存在一點(diǎn)u∈F2-F1使得(u,w)∈E(FCQn). 因此在F2-F1中存在唯一一點(diǎn)u使得(u,w)∈E(FCQn). 同理,當(dāng)F1-F2≠?時,存在唯一一點(diǎn)v∈F1-F2使得(w,v)∈E(FCQn).設(shè)X是FCQn[V(FCQn-(F1∪F2))]中的孤立點(diǎn)集,則Y=FCQn[V((FCQn)-(F1∪F2)∪X)].因此,當(dāng)F1-F2≠?時,對任意的w∈X, 有|NF1∩F2(w)|=n-1.由|F2|≤2n+1可知

|X|(n-1)≤

(|F2|-1)(n+1)≤2n(n+1)=2n2+2n.

由于n≥6,所以|X|<2n+6,若V(Y)=?,則有

2n=|V(FCQn)|=|F1∪F2|+|X|=

|F1|+|F2|-|F1∩F2|+|X|<

2(2n+1)-(n-1)+2n+6=5n+9.

當(dāng)n≥6時, 上式矛盾. 所以,V(Y)≠?. 因?yàn)镕1,F2不滿足定理3中(ⅰ)且δ(Y)≥1,所以V(Y)與F1ΔF2之間沒有邊相連.因此,F1∩F2是FCQn的點(diǎn)割且δ(FCQn-(F1∩F2))≥1,即F1∩F2是FCQn的一個1-好鄰割.根據(jù)引理5知|F1∩F2|≥2n.因?yàn)閨F1|≤2n+1,|F2|≤2n+1且F1-F2和F2-F1都非空,所以|F1-F2|=|F2-F1|=1.于是,設(shè)F1-F2={v1}和F2-F1={v2},從而對于任意的w∈X有(w,v1),(w,v2)∈E(FCQn),由引理3可知v1與v2至多有兩個公共鄰點(diǎn).因此FCQn-F1-F2至多有兩個孤立點(diǎn).下面考慮兩種情形:

情形1FCQn-F1-F2中恰有一個孤立點(diǎn)v,則(v,v1),(v,v2)∈E(FCQn)且(NFCQn(v)-{v1,v2})?F1∩F2.因?yàn)镕CQn不包含三長圈,所以

(NFCQn(v1)-{v})?F1∩F2,

(NFCQn(v2)-{v})?F1∩F2,

(NFCQn(v)-{v1,v2})∩(NFCQn(v1)-{v})=?,

(NFCQn(v)-{v1,v2})∩(NFCQn(v2)-{v})=?.

根據(jù)引理3知v1與v2至多有兩個公共鄰點(diǎn),所以|(NFCQn(v1)-{v})∩(NFCQn(v2)-{v})|≤1.因此,

|F1∩F2|≥|NFCQn(v)-{v1,v2}|+

|NFCQn(v1)-{v}|+

|NFCQn(v2)-{v}|-1=

(n-1)+n+n-1=3n-2.

于是

|F2|=|F2-F1|+|F1∩F2|≥

1+3n-2=3n-1>2n-1,n≥6.

這與|F2|≤2n+1矛盾.

情形2FCQn-F1-F2中恰有兩個孤立點(diǎn)v和v′,則

{(v,v1),(v,v2),(v′,v1),(v′,v2)}?E(FCQn),

(NFCQn(v)-{v1,v2})?F1∩F2,

(NFCQn(v′)-{v1,v2})?F1∩F2.

因?yàn)镕CQn不包含三長圈,所以

(NFCQn(v1)-{v,v′})?F1∩F2,

(NFCQn(v2)-{v,v′})?F1∩F2.

又因任意兩點(diǎn)至多有兩個公共鄰點(diǎn),所以(NFCQn(v)-{v1,v2}),(NFCQn(v′)-{v1,v2}),(NFCQn(v1)-{v,v′})和(NFCQn(v2)-{v,v′})中任意兩個集合在F1∩F2中都沒有公共點(diǎn).因此

|F1∩F2|≥|NFCQn(v)-{v1,v2}|+

|NFCQn(v′)-{v1,v2}|+

|NFCQn(v1)-{v1,v2}|+

|NFCQn(v2)-{v,v′}|=

4(n-1)=4n-4.

于是,

|F2|=|F1-F2|+|F1∩F2|≥

1+4n-4=4n-3>2n+1(n≥6).

這與|F2|≤2n+1矛盾.

綜上所述,FCQn-F1-F2中沒有孤立點(diǎn).

反證法. 假設(shè)存在兩個不同的1-好鄰故障集F1和F2,其中|Fi|≤2n+1,i=1,2,不滿足定理3中(ⅰ)～(ⅲ).不失一般性, 假設(shè)F2-F1≠?.考慮下面兩種情形:

情形1V(FCQn)=F1∪F2.

2n=|V(FCQn)|=|F1|+|F2|-|F1∩F2|≤

|F1|+|F2|≤2n+1+2n+1=4n+2.

當(dāng)n≥6時,上述不等式矛盾.

情形2V(FCQn)≠F1∪F2.

根據(jù)引理8和引理10可得下列結(jié)論:

3 結(jié)語

本文以n-維折疊交叉立方體網(wǎng)絡(luò)FCQn為研究對象,在FCQn的拓?fù)湫再|(zhì)和k(1)(FCQn)=2n,n≥4的基礎(chǔ)上,進(jìn)一步證明了在PMC模型與MM*模型下FCQn的1-好鄰診斷度分別為2n+1,n≥5和2n+1,n≥6.