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

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

1 概念和記號(hào)

設(shè)G=(V,E)是無(wú)向簡(jiǎn)單圖. 對(duì)于圖論術(shù)語(yǔ)和符號(hào)未在此定義的，遵循文獻(xiàn)[1].為方便起見(jiàn)，子集F?V稱為G的故障集.

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

由文獻(xiàn)[2]，筆者得出定理1.

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

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

文獻(xiàn)[6]筆者得出定理2.

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

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

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

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

2 連通性和診斷度

作為一個(gè)著名的互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，n維超立方體Qn有很多好性質(zhì)，如連通性、對(duì)稱性、網(wǎng)絡(luò)的高容錯(cuò)性等.

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

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

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

2016年筆者得出定理4.

定理4[8]設(shè)Qn是一個(gè)超立方體，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好鄰診斷度的問(wèn)題.

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

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

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

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

2017年，筆者得出定理7.

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

由文獻(xiàn)[15]得出定理8.

2017年，筆者得出定理9.

定理9[16]

2019年，筆者得出定理10.

定理10[17]

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

三維超Petersen圖HP3是一個(gè)Petersen圖.對(duì)于n≥4，n維超Petersen圖HPn是HPn=HPn-1?K2.

2019年，筆者得出定理11.

定理11[18]

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

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

①存在一個(gè)整數(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]設(shè)n≥7，則n維交叉立方CQn是(4n-9)兩超3限制連通的.

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

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

對(duì)換樹(shù)對(duì)應(yīng)Cayley圖，表示為CΓn.

2017年，筆者得出定理14.

定理14[21]

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

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

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

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

2016年，筆者得出定理15.

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

完全簡(jiǎn)單圖Kn對(duì)應(yīng)的Cayley圖，稱為一個(gè)巢圖，用CKn表示.

2018年，筆者得出定理16.

定理16[23]

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

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

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

2017年，筆者得出定理17.

定理17[24]

2017年，筆者得出定理18.

定理18[25]

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

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

2017年，筆者得出定理19.

定理19[26]

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

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

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

2016年，筆者得出定理20.

定理20[27]

2019年，筆者得出定理21.

定理21[28]

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

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

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

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

2017年，筆者得出定理22.

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

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

2018年，筆者得出定理23.

定理23[30]

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

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

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

2018年，筆者得出定理24.

2018年，筆者得出定理25.

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

2019年，筆者得出定理26.

由于篇幅的限制沒(méi)有列出來(lái)的，參見(jiàn)文獻(xiàn)[34-50].

2018年，筆者得出定理27.

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

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

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

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

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