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

安婷珠, 蔡學鵬, 劉夢瑤, 杜濛雨

(新疆農業大學 數理學院,新疆 烏魯木齊 830052)

眾所周知,互連網絡在平行計算及通信系統中發揮著重要作用.一個網絡的拓撲結構在數學上通常被抽象地模型化為一個圖G=(V(G),E(G)),其中:V(G)是圖的頂點集,表示網絡處理器的集合;E(G)是圖G的邊集,表示網絡的通信鏈路集.

本文中術語圖與網絡可以互換使用且所有的圖都認為是無向的、簡單的且連通的.

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

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

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

Adhikari等在文獻[15]中證明了FCQn的連通度等于n+1,n≥2.蔡等在文獻[14]中確定了k(1)(FCQn)=2n,n≥4, 馬等在文獻[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 預備知識

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

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

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

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

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

(ⅰ)當n是偶數時,un-2=vn-2;

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

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

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

(ⅱ)ul-1≠vl-1;

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

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

圖1 CQ3 和FCQ3

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

文獻[14]中證明了下面的一些結論.

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

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

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

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

2 主要結論

2.1 折疊交叉立方體網絡在PMC模型下的1-好鄰診斷度

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

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

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

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

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

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

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

當n≥5時, 上述不等式矛盾.

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

根據假設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-好鄰割.根據引理5可得|F1∩F2|≥2n. 因此,|F2|=|F2-F1|+|F1∩F2|≥2+2n=2n+2,這與|F2|≤2n+1相矛盾.

結合引理6和引理7可得下列定理:

2.2 折疊交叉立方體網絡在MM*模型下的1-好鄰診斷度

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

圖3 在MM*模型下可區分對(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設F1和F2是FCQn(n≥6)中兩個不同的1-好鄰故障集,其中|Fi|≤2n+1,i=1,2,并且F1、F2不滿足定理3中(ⅰ)～(ⅲ), 則FCQn-F1-F2中沒有孤立頂點.

證明不失一般性假設F1-F2≠?.

反證法.假設FCQn-F1-F2中至少存在一個孤立頂點w. 由于F1是一個1-好鄰故障集,所以至少存在一點u∈F2-F1使得(u,w)∈E(FCQn). 因為F1、F2不滿足定理3中(ⅲ),所以至多存在一點u∈F2-F1使得(u,w)∈E(FCQn). 因此在F2-F1中存在唯一一點u使得(u,w)∈E(FCQn). 同理,當F1-F2≠?時,存在唯一一點v∈F1-F2使得(w,v)∈E(FCQn).設X是FCQn[V(FCQn-(F1∪F2))]中的孤立點集,則Y=FCQn[V((FCQn)-(F1∪F2)∪X)].因此,當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.

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

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

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

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

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

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

根據引理3知v1與v2至多有兩個公共鄰點,所以|(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中恰有兩個孤立點v和v′,則

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

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

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

因為FCQn不包含三長圈,所以

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

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

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

|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中沒有孤立點.

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

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

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

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

當n≥6時,上述不等式矛盾.

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

根據引理8和引理10可得下列結論:

3 結語

本文以n-維折疊交叉立方體網絡FCQn為研究對象,在FCQn的拓撲性質和k(1)(FCQn)=2n,n≥4的基礎上,進一步證明了在PMC模型與MM*模型下FCQn的1-好鄰診斷度分別為2n+1,n≥5和2n+1,n≥6.