BC網(wǎng)絡(luò)的g-超條件診斷度

劉愛霞,王世英

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山西 太原 030006;2.太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院,山西 太原 030024)

0 引言

隨著半導(dǎo)體技術(shù)的飛速發(fā)展,大規(guī)模并行系統(tǒng)互連網(wǎng)絡(luò)的規(guī)模迅速擴(kuò)大,例如天河2號(hào)系統(tǒng)包含3 120 000個(gè)結(jié)點(diǎn),Cray Titan包含560 640個(gè)結(jié)點(diǎn)[1]。大規(guī)模并行計(jì)算機(jī)系統(tǒng)在使用過程中總是需要不間斷地運(yùn)行。因此,系統(tǒng)互連網(wǎng)絡(luò)具有高的容錯(cuò)性和可靠性非常重要。而且,當(dāng)系統(tǒng)中處理器發(fā)生故障時(shí),為了保持系統(tǒng)可靠性,系統(tǒng)中故障處理器需要及時(shí)被診斷出來并替換。識(shí)別故障結(jié)點(diǎn)的過程稱為系統(tǒng)的故障診斷。1967年,Preparata[2]首次將圖論方法應(yīng)用于系統(tǒng)的故障診斷,創(chuàng)建了第一個(gè)系統(tǒng)級(jí)故障診斷模型,稱為PMC模型。之后,人們提出了許多系統(tǒng)級(jí)故障診斷模型,例如Chwa 和 Hakimi模型[3]、比較模型(也稱MM模型)[4]、 BGM模型[5]等。PMC模型和MM模型是系統(tǒng)級(jí)診斷最常采用的兩個(gè)模型。

如果一個(gè)系統(tǒng)被稱為是t-可診斷的,則系統(tǒng)中故障結(jié)點(diǎn)不超過t個(gè)且不經(jīng)過替換可以一次性識(shí)別出來。使得系統(tǒng)G是t-可診斷的最大整數(shù)t稱為系統(tǒng)G的診斷度,記作t(G).作為度量大規(guī)模并行處理器系統(tǒng)的故障診斷能力的經(jīng)典參數(shù),診斷度總是假設(shè)系統(tǒng)的任一處理器的集合都可以同時(shí)發(fā)生故障。特別地,假設(shè)某個(gè)頂點(diǎn)v的所有鄰點(diǎn)同時(shí)發(fā)生故障,則此時(shí)我們將無法判斷頂點(diǎn)v是否故障。故系統(tǒng)的診斷度總是小于其最小度。然而,在大規(guī)模并行系統(tǒng)中上述情形出現(xiàn)的概率幾乎為0。因此,診斷度低估了系統(tǒng)互連網(wǎng)絡(luò)的故障診斷能力。為了更精確地度量互連網(wǎng)絡(luò)的系統(tǒng)級(jí)故障診斷能力,人們對(duì)系統(tǒng)中處理器的故障情形加以限制,提出了多種新的條件診斷度,具體參見文獻(xiàn)[6-10]。

受到g-超連通度概念的啟發(fā),Zhang等[11]假設(shè)系統(tǒng)中非故障結(jié)點(diǎn)構(gòu)成的分支的頂點(diǎn)數(shù)至少為g+1, 提出了g-超條件診斷度的概念。同時(shí),Zhang等[11]還研究了PMC和MM*模型下超立方體的g-超條件診斷度,得到了如下結(jié)果。

Bijective connection網(wǎng)絡(luò)(簡(jiǎn)稱BC網(wǎng)絡(luò))是一類基于立方體的網(wǎng)絡(luò),它包含許多著名的互連網(wǎng)絡(luò),譬如超立方體、莫比烏斯立方體、交叉立方體、紐立方體等。莫比烏斯立方體、交叉立方體、紐立方體都是超立方體的變形網(wǎng)絡(luò),它們具有更好的性質(zhì),例如它們的直徑是相同維數(shù)下的超立方體的二分之一。對(duì)BC網(wǎng)絡(luò)的性質(zhì)進(jìn)行研究,可以同時(shí)獲得超立方體、莫比烏斯立方體、交叉立方體、紐立方體等網(wǎng)絡(luò)的相關(guān)結(jié)果。因此,BC網(wǎng)絡(luò)的研究得到了廣泛的關(guān)注。本文研究了PMC和MM*模型下BC網(wǎng)絡(luò)的g-超條件診斷度。

1 術(shù)語和記號(hào)

cn(G)=max{|NG(u)∩NG(v)|:u,v∈V(G)}。

設(shè)S為頂點(diǎn)集V(G)的子集若S中任意兩點(diǎn)在G中均不相鄰,則稱S為G中獨(dú)立集。圖G中最大獨(dú)立集的階數(shù)稱為G的獨(dú)立數(shù),記作α(G)。若圖G去掉頂點(diǎn)集F后不連通,則稱F是圖G的一個(gè)割。若圖G存在割,則最小割的頂點(diǎn)數(shù)稱為圖G的連通度,記作κ(G)。否則,規(guī)定圖G的連通度κ(G)為(|V(G)|-1)。圖G中最短圈的長(zhǎng)稱為G的圍長(zhǎng),記作g(G)，未定義的術(shù)語和記號(hào)參見文[12]。

一個(gè)n維BC網(wǎng)絡(luò)Bn是一個(gè)階為2n的n-正則圖。Bn能被遞歸地定義如下[13]。

定義1[13]1維BC網(wǎng)絡(luò)B1是一個(gè)2階完全圖。1維BC網(wǎng)絡(luò)類B1={B1}。一個(gè)圖G被稱為一個(gè)n維BC網(wǎng)絡(luò),其中n≥2, 若它滿足如下條件:

(1)V(G)=V0∪V1,V0∩V1=Φ且導(dǎo)出子圖G[V0],G[V1]是(n-1)維BC網(wǎng)絡(luò);

(2)頂點(diǎn)集V0和V1之間的邊恰為圖G的一個(gè)完美對(duì)集。

所有n維BC網(wǎng)絡(luò)的集合,稱為n維BC網(wǎng)絡(luò)類,記作Βn。

圖1 兩個(gè)BC網(wǎng)絡(luò)

容易看到,n-維BC網(wǎng)絡(luò)Bn是n-正則的,且當(dāng)n≥2時(shí),它的圍長(zhǎng)是4。

下面,給出系統(tǒng)診斷的一些概念和結(jié)果。

并行計(jì)算機(jī)系統(tǒng)互連網(wǎng)絡(luò)的系統(tǒng)級(jí)故障診斷問題的研究依賴于測(cè)試模型的建立。不同的測(cè)試模型反映了實(shí)際系統(tǒng)中所采用的不同的測(cè)試方法以及對(duì)測(cè)試結(jié)果的不同解釋。在PMC模型下,相鄰的兩個(gè)處理器之間可以相互進(jìn)行測(cè)試[2]。對(duì)于系統(tǒng)G(V(G),E(G))中的兩個(gè)相鄰頂點(diǎn)u和v有序頂點(diǎn)對(duì)(u,v)代表從u到v的測(cè)試,u稱為測(cè)試者,v稱為被測(cè)試者。我們用σ(u,v)表示測(cè)試結(jié)果其中σ(u,v)取1和0,它表示被測(cè)試者是否發(fā)生故障。當(dāng)u是故障的,測(cè)試結(jié)果是不可靠的,即無論v是否發(fā)生故障,σ(u,v)可能取0,也可能取1。但當(dāng)u是非故障時(shí),若v是非故障的,則σ(u,v)為0;若v是故障的,則σ(u,v)為1。

對(duì)系統(tǒng)G的一次測(cè)試是指對(duì)G中每對(duì)相鄰點(diǎn)都進(jìn)行一次相互測(cè)試,它可以用一個(gè)有向圖T(V(G),L)表示,其中uv∈L表示u和v在圖G中相鄰。對(duì)系統(tǒng)G的一次測(cè)試T的所有測(cè)試結(jié)果的集合稱為系統(tǒng)G的一個(gè)癥狀,記作σ。換句話說,系統(tǒng)G的一個(gè)癥狀σ是一個(gè)函數(shù)σ∶L→(0,1).G中所有故障點(diǎn)的集合稱為它的故障集。顯然,它是G的頂點(diǎn)子集。

對(duì)于給定的癥狀σ, 若存在頂點(diǎn)子集F?V, 對(duì)于任意一條邊uv∈L,都有u∈VF,σ(u,v)=1當(dāng)且僅當(dāng)v∈F,則稱故障集F與癥狀σ是一致的。對(duì)不同的頂點(diǎn)子集F1和F2,若σ(F1)∩σ(F2)≠Φ,則稱F1和F2是不可區(qū)分的,F1和F2為不可區(qū)分的點(diǎn)集對(duì);否則,稱F1和F2是可區(qū)分的,F1和F2為可區(qū)分的點(diǎn)集對(duì)。

在MM模型下,一個(gè)(測(cè)試)處理器同時(shí)對(duì)它的兩個(gè)相鄰(被測(cè)試)處理器發(fā)送相同的測(cè)試任務(wù),然后比較它們反饋的測(cè)試結(jié)果,通過這樣的方式來實(shí)現(xiàn)對(duì)故障處理器的識(shí)別[4]。在MM模型下,通常有以下幾個(gè)假設(shè):

(1)所有的處理器故障都是永久的;

(2)有故障的被測(cè)試處理器對(duì)測(cè)試任務(wù)的輸出結(jié)果總是錯(cuò)誤的;

(3)由發(fā)生故障的測(cè)試處理器產(chǎn)生的比較結(jié)果是不可靠的;

(4)給兩個(gè)被測(cè)試故障處理器發(fā)送相同的測(cè)試任務(wù)或輸入總產(chǎn)生不一樣的輸出結(jié)果。

系統(tǒng)G的一個(gè)比較策略可以通過一個(gè)多重圖M(V(G),L)來模擬,其中L表示被標(biāo)記的邊的集合。 一條標(biāo)記邊(uv)w∈L表示一個(gè)由頂點(diǎn)w對(duì)頂點(diǎn)對(duì){u,v}進(jìn)行比較測(cè)試,這意味著在G中uw,vw∈E(G)。在M(V(G),L)中,所有比較的結(jié)果組成的集合稱為診斷的一個(gè)癥狀,記作σ*。在σ*中,σ*(u,v)w表示頂點(diǎn)w對(duì)被測(cè)試點(diǎn)對(duì){u,v}的輸出結(jié)果的比較結(jié)果。如果比較(uv)w的結(jié)果不一致,則σ*(u,v)w=1;否則,σ*(u,v)w=0，因此,一個(gè)癥狀σ*是一個(gè)函數(shù):σ*∶L→(0,1)。MM*模型是MM模型的一種特殊情況。在MM*模型下,G中所有可能的比較都必須被實(shí)施即 若uw,vw∈E(G), 則 (uv)w∈L。

在MM模型下,若癥狀σ*和頂點(diǎn)集F滿足下列條件:

(1)若u,v∈F且w∈V(G)F,則σ*(u,v)w=1;

(2)若u∈F且v,w∈V(G)F,則σ*(u,v)w=1;

(3)若u,v,w∈V(G)F則σ*(u,v)w=0,

則稱σ*是可由F產(chǎn)生的。若σ*可由F產(chǎn)生,則稱F與σ*是一致的。

由于發(fā)生故障的測(cè)試處理器產(chǎn)生不可靠的結(jié)果, 故一個(gè)故障集可能產(chǎn)生不同的癥狀。 令σ*(F)是與F一致的癥狀的集合。對(duì)不同的頂點(diǎn)集F1,F2?V(G), 若σ*(F1)∩σ*(F2)=?,則稱F1和F2是可區(qū)分的,F1和F2為可區(qū)分的點(diǎn)集對(duì); 否則稱F1和F2是不可區(qū)分的,F1和F2為不可區(qū)分的點(diǎn)集對(duì)。

定義2[2]設(shè)G是一個(gè)互連網(wǎng)絡(luò)。在不被替換的情況下,如果G中故障結(jié)點(diǎn)的個(gè)數(shù)不超過t時(shí),所有故障都能被一次性診斷出來,則稱網(wǎng)絡(luò)G是t-可診斷的。系統(tǒng)G的診斷度是使得G是t-可診斷的t的最大值,記作t(G)。

在文[6]中,Lai等給出了網(wǎng)絡(luò)G是t-可診斷的一個(gè)等價(jià)定義。

定義3[6]網(wǎng)絡(luò)G是t-可診斷的當(dāng)且僅當(dāng)G中任意兩個(gè)滿足|F1|≤t,|F2|≤t的頂點(diǎn)集F1,F2都是可區(qū)分的。

為了更精確地度量互連網(wǎng)絡(luò)的故障診斷能力,Lai等[6]提出了條件診斷度的概念。

定義4[6]設(shè)F是網(wǎng)絡(luò)G=(V,E)的一個(gè)頂點(diǎn)子集。若G中任意一個(gè)頂點(diǎn)v的鄰集均不包含于F則稱F為G的一個(gè)條件集。若G中任意兩個(gè)滿足|F1|≤t,|F2|≤t的條件集F1,F2都是可區(qū)分的,則網(wǎng)絡(luò)G是條件t-可診斷的。網(wǎng)絡(luò)G的條件診斷度是使得G是條件t-可診斷的t的最大值,記作tc(G).

受條件診斷度和g-超連通度概念的啟發(fā),Zhang等[11]對(duì)分支的結(jié)點(diǎn)數(shù)加以限制,提出了g超條件診斷度的概念。

引理1[16]設(shè)F1,F2是圖G的兩個(gè)相異的頂點(diǎn)子集。頂點(diǎn)集F1和F2在PMC模型下是可區(qū)分的當(dāng)且僅當(dāng)存在頂點(diǎn)u∈V(F1∪F2),v∈F1ΔF2使得uv∈E(G), 如圖2。

圖2 PMC模型下的可區(qū)分點(diǎn)對(duì)(F1,F2)

Sengupta和Dahbura[17]給出了MM*模型下頂點(diǎn)集F1和F2可區(qū)分的一個(gè)充要條件。

引理2[17]設(shè)F1,F2是圖G的兩個(gè)相異的頂點(diǎn)子集。頂點(diǎn)集F1和F2在MM*模型下是可區(qū)分的當(dāng)且僅當(dāng)下列情形之一成立(如圖3):

圖3 MM*模型下的可區(qū)分點(diǎn)對(duì)(F1,F2)

2 BC網(wǎng)絡(luò)在PMC和MM*模型下的g-超條件診斷度的下界

本節(jié),我們將在BC網(wǎng)絡(luò)的容錯(cuò)性的已有結(jié)果的基礎(chǔ)上,進(jìn)一步討論BC網(wǎng)絡(luò)在PMC和MM*模型下的g-超條件診斷度的下界。 首先,介紹Fan等[13]得到的BC網(wǎng)絡(luò)Bn的(g+1)階子圖的鄰集的性質(zhì)。

2012年,Yang等[18]研究了Bn的g-超連通度,給出了它的一個(gè)下界。

下面的函數(shù)在Bn的g-超條件診斷度的研究中具有重要的作用。通過簡(jiǎn)單的計(jì)算,容易得到下面的引理。

(1)當(dāng)1≤g≤n-1時(shí),函數(shù)φ(g)嚴(yán)格單調(diào)遞增;

下面,我們給出一個(gè)簡(jiǎn)單的引理。

引理6 當(dāng)n≥1時(shí),BC網(wǎng)絡(luò)Bn的獨(dú)立數(shù)α(Bn)≤2n-1。

下面,我們討論P(yáng)MC模型下Bn的g-超條件診斷度的下界。

|V(Bn)|-|F1∪F2|≥

注意到F2F1≠?且Bn[F2F1]的每個(gè)分支包含至少(g+1)個(gè)頂點(diǎn),故|F2F1|≥g+1，因此

|F2|=|F1∩F2|+|F2F1|≥

與F2的取法矛盾。證畢。

|V(Bn)|-|F1∪F2|≥

圖4 斷言1中V(G)的分解

由引理6,|W|≤2n-1，從而,對(duì)任意的w∈W,NBn(w)?F1∪F2。下證F1F2≠?，否則,NBn(w)?F2。由此可知w是Bn-F2中的孤立點(diǎn)。故g=0, 與題設(shè)g≥1矛盾。類似地,F2F1≠?。因此,

|F1∩F2|=|F1|-|F1F2|≤

(1)

設(shè)w為W中一點(diǎn)。假設(shè)|NBn(w)∩(F1F2)|≥2,則存在u,v∈F1F2使得uw,vw∈E(Bn).由引理 2(2),(F1,F2)是可區(qū)分的,與(F1,F2)不可區(qū)分矛盾。故|NBn(w)∩ (F1F2)|≤1。若|NBn(w)∩(F1F2)|=0,則NBn(w)?F2，從而推出w是Bn-F2中的孤立點(diǎn),即g=0,與題設(shè)g≥1矛盾。故

|NBn(w)∩(F1F2)|=1。

同理可得

|NBn(w)∩(F2F1)|=1。

因此,

|NBn(w)∩(F1∩F2)|=

|NBn(w)|-|NBn(w)∩(F1F2)|-

|NBn(w)∩(F2F1)|=

|NBn(w)|-2=n-2。

由此可得,

|F1∩F2|≥|NBn(w)∩(F1∩F2)|=n-2。

設(shè)U=V(Bn)(F1∪F∪W).下證U≠?.反之假設(shè)U=?，則

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

|F1∩F2|+|W|≤

由引理4,

|F1F2|≤g且 |F2F1|≤g。

|F1∩F2|≥|NF1∩F2(W)|≥

|NF1∩F2(W′)|≥

|NBn(W′)|-|F1F2|-|F2F1|≥

再由(1)可以推出

|V′|-1=|F1F2|+|F2F1|+

另一方面,因?yàn)镕1和F2都是Bn中的g-超割且U和V′之間無邊,所以|W|+|F1F2|≥g+1,|W|+|F2F1|≥g+1。再由F1F2≠?和F2F1≠?,我們有

|V′|-1=|F1F2|+|F2F1|+

|W|-1≥g+1。

顯然,NBn(V′)?F1∩F2。故|NBn(V′)|≤|F1∩F2| .由引理3和引理5(2),

|F1∩F2|≥|NBn(V′)|≥

也就是

然而,由題設(shè)可知,

矛盾。斷言證畢。

另一方面,因?yàn)镕1∩F2是Bn的g超割,所以|F1F2|≥g+1，從而,

|F1|=|F1∩F2|+|F1F2|≥

與F1的取法矛盾。證畢。

結(jié)合定理3、定理4和引理7可得PMC和MM*模型下超立方體Qn的g-超條件診斷度。

推論1設(shè)n,g是兩個(gè)整數(shù),則

顯然,推論1(1)是定理1, 推論1(2)改進(jìn)了定理 2。 另外,推論1表明定理3和定理4給出BC網(wǎng)絡(luò)的g-超條件診斷度的下界是緊的。

3 g較小時(shí),BC網(wǎng)絡(luò)在PMC和MM*模型下的g-超條件診斷度

本節(jié)進(jìn)一步討論了當(dāng)1≤g≤3時(shí),BC網(wǎng)絡(luò)在PMC和MM*模型下的g-超條件診斷度。應(yīng)用所得結(jié)果,許多著名的互連網(wǎng)絡(luò)的g(1≤g≤3)超條件診斷度被給出,譬如交叉立方體、莫比烏斯立方體和紐立方體等。為了得到本節(jié)的主要結(jié)果,我們首先介紹BC網(wǎng)絡(luò)一些重要的性質(zhì)。

引理8[19]設(shè)Bn∈Βn，則

(1)|V(Bn)|=2n;

(2)Bn是n-正則的;

(3)當(dāng)n≥2時(shí),cn(Bn)=2且Bn的圍長(zhǎng)為4;

為了敘述方便,我們用Pt表示階為t的路,用Kt表示t個(gè)頂點(diǎn)的完全圖。

引理9[20]設(shè)Bn∈Βn，則

(1)設(shè)K1和P3為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥2,則cnBn(K1,P3)≤4;

(2)設(shè)K2和P3為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(K2,P3)≤7;

(3)設(shè)K1和K1,3為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(K1,K1,3)≤5;

(4)設(shè)K1和P4為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(K1,P4)≤5;

(5)設(shè)K2和K1,3為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(K2,K1,3)≤9;

(6)設(shè)K2和P4為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(K2,P4)≤9;

(7)設(shè)P3和K1,3為B6中兩個(gè)頂點(diǎn)不相交的子圖,則cnB6(P3,K1,3)≤12;

(8)設(shè)P3和P4為B6中兩個(gè)頂點(diǎn)不相交的子圖,則cnB6(P3,P4)≤12;

(9)設(shè)P3和K1,3為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(P3,K1,3)≤13;

(10)設(shè)P3和P4為Bn中兩個(gè)頂點(diǎn)不相交的子圖且n≥3,則cnBn(P3,P4)≤13。

假設(shè)H∈Βk,Bn∈Βn, 其中k

證明因?yàn)镠∈Β2是Bn的成分子圖,所以由定義可知存在Bn的成分子圖序列G0∈Β2,G1∈Β3,…,Gn-3∈Βn-1使得(…(((H?G0)?G1)?G2)?…)?Gn-3=Bn。設(shè)H1=H?G0,H2=H1?G1,…,Hn-2=Hn-3?Gn-3=Bn，顯然,H是Hi的子圖且對(duì)任意的1≤i≤n-2,V(T)?V(Hi)，因?yàn)镠1=H?G0,所以

|NH1(V(T))|=|NH(V(T))|+|V(T)|。

類似地,我們有

|NH2(V(T))|=|NH1(V(T))|+|V(T)|,

…

|NHn-2(V(T))|=|NHn-3(V(T))|+|V(T)|。

考慮g=1的情形。設(shè)V(T)={x1,x2}，下證G不包含孤立點(diǎn)。否則,假設(shè)u是G中的一個(gè)孤立點(diǎn)。從而,NBn(u)?NBn(T),即NBn(u)?NBn(u)∩NBn(T).由引理8(3)可知cn(Bn)=2, 故6≤n=|NBn(u)|=|NBn(u)∩NBn(T)|≤4矛盾。因此,G中不含孤立點(diǎn)。因此,此時(shí)NBn(V(T))是一個(gè)R1-割。

考慮g=2的情形。設(shè)T=P3=x1x2x3，下面首先證明G不包含孤立點(diǎn)。反之,假設(shè)G包含孤立點(diǎn)u.引理8和引理9(1),我們有6≤n=|NBn(u)|=|NBn(u)∩NBn(P3)|≤4, 矛盾。因此G中不含孤立點(diǎn)。若G中包含一條孤立邊K2, 則由引理8,引理9(2)和n≥6, 我們有10≤2n-2=|NBn(K2)|=|NBn(K2)∩NBn(P3)|≤7,矛盾。因此,此時(shí)NBn(V(T))是一個(gè)R2-割。

觀察1設(shè)T=K1,3∈Q3或T是G(8,4)中的一條路xyzw,如圖5所示，則 |NB3(T)|=3。

圖5 Q3和G(8,4)的子圖T

引理11設(shè)H∈Β3是n維BC圖Bn的成分子圖,其中n≥6, 且設(shè)T是H的子圖使得當(dāng)H=Q3時(shí),T?K1,3;否則,設(shè)T=xyzw如圖5(b)所示，則|NBn(V(T))|=4n-9且NBn(V(T))是一個(gè)R3-割。

證明因?yàn)镠∈Β3是n維BC圖Bn的成分子圖,所以由定義可知,存在成分子圖的序列G0∈Β3,G1∈Β4,…,Gn-4∈Βn-1使得(…(((H?G0)?G1)?G2)?…)?Gn-4=Bn。設(shè)H1=H?G0,H2=H1?G1,…,Hn-3=Hn-4?Gn-4=Bn，顯然,H是Hi的子圖且對(duì)任意的1≤i≤n-3有V(T)?V(Hi)。

因?yàn)镠1=H?G0,所以|NH1(V(T))|=|NH(V(T))|+|V(T)|。同理,|NH2(V(T))|=|NH1(V(T))|+|V(T)|,…,|NHn-3(V(T))|=|NHn-4(V(T))|+|V(T)|。將前面各式依次迭代相加可得,|NHn-3(V(T))|=|NH(V(T))|+4(n-3)。由觀察1,我們有|NBn(V(T))|=4n-9，令G=Bn-CBn(V(T))。

下證G中不含孤立點(diǎn)、孤立邊和孤立的路P3。

因?yàn)閚≥6所以|V(G)|=2n-(4n-9)>0, 從而G非空。假設(shè)G中包含一個(gè)孤立點(diǎn)u，則由引理8和引理9(3)和(4)可得,6≤|NBn(u)|=|NBn(u)∩NBn(T)|≤5,矛盾。因此,G中不含孤立點(diǎn)。

現(xiàn)在,假設(shè)G中包含一條孤立邊K2，由引理9(5)和(6),有10≤2×6-2≤|NBn(K2)|=|NBn(K2)∩NBn(T)|≤9,矛盾。因此,G中不含孤立邊。

最后,假設(shè)G中包含一條孤立路P3，此時(shí),我們分兩種情況進(jìn)行討論。

情況1n=6。

因?yàn)锽6是6-正則的且cn(B6)=2,所以|NB6(P3)|=3×6-5=13。再由引理9(7)和(8),我們有13=|NB6(P3)|=|NB6(P3)∩NB6(T)|≤12,矛盾。

情況2n≥7。

因?yàn)锽n是n-正則且cn(Bn)=2,所以|NBn(P3)|=3×n-5≥16。另一方面,由引理9(9)和(10),我們有|NBn(P3)|=|NBn(P3)∩NBn(T)|≤13,矛盾。

因此,NBn(T)是一個(gè)R3-割。證畢。

由定理3、4和引理12,我們可以推出Bn在PMC和MM*模型下的g-超條件診斷度。

表1 部分BC網(wǎng)絡(luò)在PMC和MM*模型下的g-超條件診斷度,其中g(shù)=1,2,3

4 結(jié)論