互連網(wǎng)絡的連通性和診斷度

(山西師范大學 數(shù)學與計算機學院, 山西 臨汾 041004)

在科學與工程計算領域，海量數(shù)據(jù)的處理和復雜問題的解決對計算機的計算能力的要求日益提高，并且這些需求的增長速度已經(jīng)遠遠超出了微處理機的發(fā)展速度.在此背景下, 并行計算機系統(tǒng)應運而生并得到快速發(fā)展.并行計算機系統(tǒng)常以某個具有優(yōu)良性質(zhì)的互連網(wǎng)絡為底層拓撲結構進行構建.互連網(wǎng)絡的性能對整個系統(tǒng)的硬件消耗、通信性能、路由算法的可行性都起著重要的甚至是決定性的作用，以至于并行計算機系統(tǒng)的設計理念已經(jīng)由以CPU為主逐步讓位于以互連網(wǎng)絡為主.并行計算機系統(tǒng)中元器件之間的連接模式稱為該系統(tǒng)的互連網(wǎng)絡，簡稱網(wǎng)絡.從拓撲上講，一個系統(tǒng)的互連網(wǎng)絡邏輯上指定了該系統(tǒng)中所有元器件之間的連接方式.互連網(wǎng)絡可以看成一個圖，圖的頂點表示系統(tǒng)中的元器件或處理器， 圖的邊表示元件之間的物理連線.因此，網(wǎng)絡拓撲的性能可以通過圖的性質(zhì)和參數(shù)來度量.網(wǎng)絡出現(xiàn)故障是不可避免的.由此，互連網(wǎng)絡的連通性和故障診斷是一個重要的研究課題.

1 概念和記號

設G=(V,E)是無向簡單圖. 對于圖論術語和符號未在此定義的，遵循文獻[1].為方便起見，子集F?V稱為G的故障集.

定義1設G=(V,E)是一個連通圖. 對于一個故障集F?V， 如果|N(v)∩(VF)|≥g對于VF的每一個點v，則故障集F稱為一個g好鄰故障集. 對于G的一個g好鄰故障集F，如果G-F是不連通的，則稱F為G的一個g好鄰割. 如果G有一個g好鄰割，則稱G為g好鄰連通的.對于一個g好鄰連通圖G，G的g好鄰連通度是G的最小g好鄰割的基數(shù)，用κ(g)(G)表示.

由文獻[2]，筆者得出定理1.

對于多重處理器系統(tǒng)，一些處理器可能在系統(tǒng)中失效和處理器故障的識別在可靠計算中起重要作用.識別的過程稱為系統(tǒng)診斷.幾種診斷模型被提出來識別故障處理器.一種方法是Preparata等[3]提出的Preparata、Metze和Chien(PMC)診斷模型.系統(tǒng)的診斷是通過兩個相互連接的處理器來實現(xiàn)的.診斷那個系統(tǒng)G，G中的兩個相鄰節(jié)點能夠執(zhí)行相互測試.對于V(G)中兩個相鄰的節(jié)點u和v，執(zhí)行u測試v由有序對(u,v)表示.如果u測試v評估為故障(分別為無故障)，則測試(u,v)的結果為1(分別為0).在PMC模型中，通常假設測試結果是可靠的(分別是不可靠的)如果節(jié)點u無故障(分別是故障的).系統(tǒng)G的測試作業(yè)T是一個集合對每對相鄰頂點的測試.建模為有向測試圖T=(V(G),L)，其中(u,v)∈L中暗示u和v在G中相鄰.測試作業(yè)的所有測試結果的集合T被稱為診斷子. 形式上，診斷子是一個函數(shù)σ:L{0,1}.那個系統(tǒng)中的所有故障處理器的集合稱為故障集.這可以是V(G)的任何子集.對于給定的診斷子σ，頂點子集F?V(G)被說與σ一致，如果診斷子σ可根據(jù)下面的情況產(chǎn)生，對于(u,v)∈L使得u∈VF，σ(u,v)=1當且僅當v∈F.這意味著F是一個可能的故障處理器集合.由于故障處理器產(chǎn)生的測試結果是不可靠的，給定的一組F的故障頂點可能會產(chǎn)生很多不同的診斷子.另一方面，不同故障集可能會產(chǎn)生相同的診斷子.讓σ(F)表示與F相一致的的所有診斷子的集合.在PMC模型中，V(G)中的兩個不同的集合F1和F2被說是可區(qū)分的如果σ(F1)∩σ(F2)=?.否則，F(xiàn)1和F2被說是不可區(qū)分的.另外，我們說 (F1,F2)是可區(qū)分對如果σ(F1)∩σ(F2)=?； 否則，(F1,F2)是不可區(qū)分對.

另一個主要方法，即比較診斷模型(MM模型)，由Maeng等[4]提出.在MM模型中，處理器將相同的任務發(fā)送給一對不同的鄰居，然后比較它們的響應以診斷系統(tǒng)G=(V(G),E(G)).G的比較方案被建模為多重圖，由M=(V(G),L)表示，其中L是標記邊集.一條標號邊(u,v)w∈L中表示比較，其中，兩個頂點u和v由頂點w比較，這意味著uw,vw∈E(G).M=(V(G),L)中所有比較結果的集合稱為診斷子，用σ表示.如果比較(u,v)w不同意，那么σ(u,v)w=1.否則，σ(u,v)w=0.因此，診斷子是從L到0,1的函數(shù). Anton等[5]提出MM*模型.它是MM模型的一個特殊情況.在MM*中，每個節(jié)點必須測試其相鄰節(jié)點的所有對，如果uw,vw∈E(G)，則(u,v)w∈L.對于給定的診斷子σ，一個頂點的子集F?V(G)被認為與σ一致如果診斷子σ可以從那種情況中產(chǎn)生， 對于任意 (u,v)w∈L使得w∈VF,σ(u,v)w=1當且僅當u和v至少有一個是在F中.讓σ(F)表示與F一致的所有診斷子的集合.設F1和F2是V(G)中的兩個不同的集合.如果σ(F1)∩σ(F2)=?，那么，(F1,F2)是可區(qū)分對；否則，(F1,F2)是不可區(qū)分對.

文獻[6]筆者得出定理2.

定義4一個系統(tǒng)G=(V,E)在頂點x處是局部t可診斷的, 如果診斷子σF是由包含頂點x的故障集F產(chǎn)生的且|F|≤t, 每一個與σF一致的故障集F′都必須包含頂點x且|F′|≤t.

定義5在一個系統(tǒng)G=(V,E)中頂點x局部診斷度tl(x)是G在x處局部t可診斷的最大t值.

定義6x表示圖G=(V,E)中的一個頂點. 如果x的局部診斷度等于它的度， 即tl(x)=dG(x), 那么稱x具有強局部診斷性質(zhì).

定義7設G=(V,E)是一個圖. 如果G中每個頂點的局部診斷度等于該頂點在圖G中的度， 即tl(x)=dG(x)， 那么稱G具有強局部診斷性質(zhì).

2 連通性和診斷度

作為一個著名的互連網(wǎng)絡的拓撲結構，n維超立方體Qn有很多好性質(zhì)，如連通性、對稱性、網(wǎng)絡的高容錯性等.

一個n維超立方體Qn(n≥1)是一個圖.其頂點集是0和1的所有n元組的集合；如果兩個頂點準確地不同在一個坐標，那么它們是相鄰的.

2012年, Peng等[7]提出了一種多處理器系統(tǒng)故障診斷方法，即g好鄰診斷度，它要求每個無故障節(jié)點至少有g個無故障鄰點.由文獻[7]得出定理3.

定理3[7]設Qn是一個超立方體和0≤g≤n-3，則tg(Qn)=(n-g+1)2g-1在PMC模型下.

2016年筆者得出定理4.

定理4[8]設Qn是一個超立方體，n≥5和0≤g≤n-3，則tg(Qn)=(n-g+1)2g-1在MM*模型下.

2015年，筆者得出定理5.

2016年，筆者得出定理6.

定理6[13]

定理3～6完全解決了k元n立方的g好鄰診斷度的問題.

對于一個整數(shù)n≥1，長度為n的二進制字符串表示為u1u2…un，其中,ui∈{0,1}對于任意一個整數(shù)i∈{1,2,…,n}.n維局部扭立方，表示為LTQn，是2n個頂點和n2n-1邊的n正則圖.它能遞歸地定義如下：

對于n≥2，一個n維局部扭立方LTQn按遞歸方式定義如下：

①LTQ2是由分別標記為00、01、10和11的四個節(jié)點組成的圖，連接由四條邊 {00,01}、{01,11}、{11,10}和{10,00}.

②對于n≥3，LTQn是由兩個不相交的LTQn-1拷貝構成，按照以下步驟：0LTQn-1表示給LTQn-1的一個拷貝的每個節(jié)點的標號前加0獲得的圖.1LTQn-1表示給LTQn-1的一個拷貝的每個節(jié)點的標號前加1獲得的圖.連接0LTQn-1的每個節(jié)點 0u2u3…un到1LTQn-1的節(jié)點1(u2+un)u3…un，其中“+”表示模2加法.

2017年，筆者得出定理7.

定理7[14]設n≥3和0≤g≤n-3，則n維局部扭立方LTQn的g好鄰診斷度tg(LTQn)=2g(n-g+1)-1在PMC模型和MM*模型下.

由文獻[15]得出定理8.

2017年，筆者得出定理9.

定理9[16]

2019年，筆者得出定理10.

定理10[17]

圖G1和G2的Cartesian積是一個圖G1?G2.它的頂點集是{(x,y):x∈V(G1),y∈V(G2)}.在G1?G2中， 頂點(x1,y1)和(x2,y2)是相鄰的當且僅當x1=x2和y1y2∈E(G2) 或者x1x2∈E(G1)和y1=y2.

三維超Petersen圖HP3是一個Petersen圖.對于n≥4，n維超Petersen圖HPn是HPn=HPn-1?K2.

2019年，筆者得出定理11.

定理11[18]

設R={(00,00)、(10,10)、(01,11)、(11,01)}. 兩位二進制字符串u=u1u0和v=v1v0是對相關的，表示為u～v，當且僅當 (u,v)∈R.

一個n維交叉立方體立方CQn， 它的頂點集是{vn-1vn-2…v0:0≤i≤n-1,vi∈{0,1}}.頂點u=un-1un-2…u0和v=vn-1vn-2…v0是相鄰的當且僅當滿足以下條件之一.

①存在一個整數(shù)l(1≤l≤n-1)使得

1)un-1un-2…ul=vn-1vn-2…vl；

2)ul-1≠vl-1；

3) 如果l是偶數(shù)，則ul-2=vl-2；

②

1)un-1=vn-1；

2) 如果l是偶數(shù)，則un-2=vn-2；

2018年，筆者得出定理12.

定理12[19]

2019年，筆者得出定理13.

定理13[20]設n≥7，則n維交叉立方CQn是(4n-9)兩超3限制連通的.

設G是一個有限群，S是G不含單位元的生成集.Cayley有向圖Cay(S,G) 定義如下: 它的頂點集是G，孤集是{(g,gs):g∈G,s∈S}.若對任意的s∈S，有s-1∈S，則稱這個Cayley圖為無向Cayley圖.本文所說的Cayley圖均為無向Cayley圖，且假定S的元是對換，則S生成的置換群是對稱群Sn的子群，它的單位元記為(1).它是頂點傳遞的.由于對換可用圖直觀的表示出來，所以引入下面的概念.

考慮一個n≥3 階連通簡單圖H，它的頂點集為{1,2,…,n}，它的每條邊可視為Sn中的一個對換，這樣H的邊集E(H)，就對應了Sn中的一個對換集S.在這個意義下，把H稱為對換簡單圖.Cayley圖Cay(S,)稱為H對應的Cayley圖. 當對換簡單圖是樹時,稱為對換樹. 當對換簡單圖是路時, 它對應的Cayley圖稱為泡型圖 (Bubble sort graph).當對換簡單圖是星時, 它對應的Cayley圖稱為星圖 (Star graph).由于n階對換樹對應的Cayley圖都是Sn上的Cayley圖，故任意一個n階對換簡單圖對應的Cayley圖也是Sn上的Cayley圖.

對換樹對應Cayley圖，表示為CΓn.

2017年，筆者得出定理14.

定理14[21]

(1)設n≥3，則CΓn的自然連通度是κ(1)(CΓn)=2n-4.

(2)設n≥4，則CΓn的自然診斷度是t1(CΓn)=2n-3在PMC模型下.

(3)設n≥4，則，除去泡型圖B4，t1(CΓn)=2n-3在MM*模型下.

(4)B4的自然診斷度是t1(B4)=4在MM*模型下.

2016年，筆者得出定理15.

定理15[22]設n≥4，則CΓn的2好鄰診斷度是t2(CΓn)=g(n-2)-1在PMC模型和MM*下.其中g是CΓn的圍長.

完全簡單圖Kn對應的Cayley圖，稱為一個巢圖，用CKn表示.

2018年，筆者得出定理16.

定理16[23]

(1)設n≥4，則巢圖CKn的自然連通度是κ(1)(CKn)=n2-n-2.

(2)設n≥4，則CKn的自然診斷度是t1(CKn)=n2-n-1在PMC模型下.

(3)設n≥5，則CKn的自然診斷度是t1(CKn)=n2-n-1在MM*模型下.

2017年，筆者得出定理17.

定理17[24]

2017年，筆者得出定理18.

定理18[25]

(1)設n≥4，則n維泡型星圖BSn的自然診斷度是t1(BSn)=4n-7在PMC模型下.

(2)設n≥5，則BSn的自然診斷度是t1(BSn)=4n-7在MM*模型下.

2017年，筆者得出定理19.

定理19[26]

(1)設n≥5，則n維泡型星圖BSn的2好鄰連通度是κ(2)(BSn)=8n-22.

(2)κ(2)(BS4)=8.

(3)設n≥5，則t2(BSn)=8n-19在PMC模型和MM*模型下.

2016年，筆者得出定理20.

定理20[27]

2019年，筆者得出定理21.

定理21[28]

(1)設n≥4，則n維泡型圖Bn的自然診斷度是t1(Bn)=2n-3在PMC模型下.

(2)設n≥5，則Bn的自然診斷度是t1(Bn)=2n-3在MM*模型下.

(3)設n≥4，則Bn的2好鄰診斷度是t2(Bn)=4n-9在PMC模型和MM*模型下.

(4)設n≥7，則Bn的3好鄰診斷度是t3(Bn)=8n-25在PMC模型和MM*模型下.

2017年，筆者得出定理22.

定理22[29]設n≥4和0≤g≤n-2，則星圖Sn的g好鄰診斷度是tg(Sn)=(g+1)!(n-g)-1在PMC模型和MM*模型下.

交錯群An是對稱群Sn的一個子群.它由整個的偶置換組成.我們知道{(12i),(1i2):i=3,4,…,n}是An的一個生成集.n維交錯群圖AGn， 它的點集V(AGn)=An； 它的兩點u,v相鄰當且僅當u=v(12i)或者u=v(1i2)，3≤i≤n.

2018年，筆者得出定理23.

定理23[30]

(1)設n≥5，則n維交錯群圖AGn的然診斷度是t1(AGn)=4n-10 在PMC模型和MM*模型下.

(2)t1(AG4)=5在PMC模型下.

(3)t1(AG4)=4在MM*模型下.

2018年，筆者得出定理24.

2018年，筆者得出定理25.

定理25[32]設n≥5，則n維交錯群圖AGn的2好鄰診斷度是t2(AGn)=6n-16在PMC模型和MM*模型下.

2019年，筆者得出定理26.

由于篇幅的限制沒有列出來的，參見文獻[34-50].

2018年，筆者得出定理27.

定理27[51]n維交錯群圖AGn有強局部診斷性和保持這個強局部診斷性即使存在(2n-7)遺失邊在它在MM*模型下.

2019年，筆者得出定理28～32.

定理28[52]n維泡型星圖BSn(n≥5)有強局部診斷性和保持這個強局部診斷性即使存在(2n-5)遺失邊在它在MM*模型下.這個結果是最優(yōu)的.

定理29[53]排列圖An,k有強局部診斷性和保持這個強局部診斷性即使存在((k-1)(n-k)-1)遺失邊在它在MM*模型下.這個結果是最優(yōu)的.

定理30[54]交換超立方體EH(s,t)) (2≤s≤t和s=1,t=2)有強局部診斷性在MM*模型下.