梁家榮白 楊王新陽(yáng)

①(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 南寧 530004)

②(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 廣州 510006)

評(píng)估交換超立方體網(wǎng)絡(luò)可靠性的一種新方法

梁家榮*①白 楊①王新陽(yáng)②

①(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 南寧 530004)

②(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 廣州 510006)

交換超立方體互連網(wǎng)絡(luò)(EH(s,t))作為大規(guī)模處理器系統(tǒng)網(wǎng)絡(luò)模型的重要候選之一，其可靠性問(wèn)題一直為人們所關(guān)注。該文利用額外連通度作為評(píng)價(jià)可靠性的重要度量，對(duì)交換超立方體互連網(wǎng)絡(luò)的可靠性進(jìn)行分析，得到了交換超立方體網(wǎng)絡(luò)的2-額外點(diǎn)連通度(k2(EH(s,t)))和2-額外邊連通度(λ2(EH(s,t )))，證明了當(dāng)t≥s≥2時(shí)，k2(EH(s,t))=3s-2；當(dāng)t≥s≥3時(shí)，λ2(EH(s,t))=3s-1。分析說(shuō)明了對(duì)交換超立方體互連網(wǎng)絡(luò)的可靠性評(píng)價(jià)時(shí)，2-額外連通度較之傳統(tǒng)連通度更具有優(yōu)勢(shì)性。

互連網(wǎng)絡(luò)；交換超立方體；可靠性；額外連通度

1 引言

互連網(wǎng)絡(luò)的可靠性主要是指在網(wǎng)絡(luò)的部分節(jié)點(diǎn)、部分鏈路出現(xiàn)故障時(shí)，剩余子網(wǎng)是否仍能保持正常通信的能力。隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)中出現(xiàn)故障節(jié)點(diǎn)、故障鏈路的情況不可避免，因此網(wǎng)絡(luò)的可靠性問(wèn)題就成為不可回避的研究課題。其中，點(diǎn)連通度和邊連通度是衡量網(wǎng)絡(luò)可靠性的兩個(gè)重要參數(shù)，它們表明了一個(gè)網(wǎng)絡(luò)能容忍同時(shí)故障的最大節(jié)點(diǎn)數(shù)和最大鏈路數(shù)。但點(diǎn)連通度和邊連通度在衡量網(wǎng)絡(luò)可靠性方面也存在不足的地方：它們都默認(rèn)一個(gè)節(jié)點(diǎn)或一條鏈路的所有鄰居節(jié)點(diǎn)(或鄰居鏈路)可能同時(shí)出現(xiàn)故障，而這種情況在實(shí)際的網(wǎng)絡(luò)中幾乎不可能存在，例如在一個(gè)具有2n個(gè)節(jié)點(diǎn)的正則度為n的規(guī)則互連網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)的所有鄰居點(diǎn)同時(shí)故障的概率是2n/＜10-6(當(dāng)n≥6時(shí))，這種概率的事件幾乎不可能發(fā)生，因此用點(diǎn)連通度和邊連通度研究互連網(wǎng)絡(luò)的可靠性不切實(shí)際。

為了解決這一問(wèn)題，Haray在傳統(tǒng)連通度的基礎(chǔ)上加入一些限制條件，提出了條件連通度[1]的概念。后來(lái)，F(xiàn)abrega和Fiol將這一限制條件進(jìn)一步細(xì)化提出了額外連通度的概念[2,3]。額外連通度一經(jīng)提出便引起眾多學(xué)者的高度關(guān)注，并獲得眾多研究成果[4-10]。文獻(xiàn)[4]研究了超立方體[11]的2-額外連通度；文獻(xiàn)[5]將超立方體的額外連通度精確到了h階，這極大提升了超立方體網(wǎng)絡(luò)的可靠性精度；文獻(xiàn)[6]從網(wǎng)絡(luò)中不存在孤立節(jié)點(diǎn)、孤立鏈路的角度分別研究了折疊超立方體網(wǎng)絡(luò)[12]的2-額外點(diǎn)連通度和2-額外邊連通度；文獻(xiàn)[9]研究了一類特殊正則網(wǎng)絡(luò)的2-額外連通度；文獻(xiàn)[10]則將該類特殊正則網(wǎng)絡(luò)的可靠性精度提升到h階，證明了當(dāng)0≤h≤n-4時(shí)，n維一一對(duì)應(yīng)連接(Bijection Connected,BC)網(wǎng)絡(luò)[13]的h-額外連通度是n(h+1)-(h(h+3))/2，這為進(jìn)一步研究更大規(guī)模的具有失效節(jié)點(diǎn)的BC互連網(wǎng)絡(luò)的可靠性提供了支持。

在眾多互連網(wǎng)絡(luò)結(jié)構(gòu)中，超立方體是最具吸引力的網(wǎng)絡(luò)之一，但它并非各方面性質(zhì)最好的。針對(duì)超立方體的一些缺陷，不少學(xué)者提出了很多超立方體的變種[12,14-17]。作為其中最重要的網(wǎng)絡(luò)之一，交換超立方體[17]不僅保持了超立方體大量的優(yōu)秀屬性，并且擁有比超立方體更好的屬性，如其邊數(shù)幾乎是超立方體邊數(shù)的一半。目前，關(guān)于交換超立方體互連網(wǎng)絡(luò)的研究已經(jīng)有很多成果[18-21]，其中可靠性問(wèn)題備受人們關(guān)注。文獻(xiàn)[18]證明了交換超立方體的點(diǎn)連通度和邊連通度均為1s+；在文獻(xiàn)[19]中，Ma等人從網(wǎng)絡(luò)中不存在孤立節(jié)點(diǎn)的角度證明了交換超立方體網(wǎng)絡(luò)的超點(diǎn)連通度和超邊連通度均為2s，這將交換超立方體網(wǎng)絡(luò)的可靠性的精度提升了近2倍。盡管如此，但上述參數(shù)仍有一定缺陷，例如當(dāng)n很大時(shí)，交換超立方體的連通度1s+和超連通度2s與節(jié)點(diǎn)總數(shù)2s+t+1的比值均非常小，以至于失去了實(shí)際意義，而額外連通度在一定程度上克服了這一缺陷。因此用額外連通度來(lái)研究交換超立方體的可靠性具有較高的學(xué)術(shù)意義和應(yīng)用價(jià)值。本文主要在傳統(tǒng)連通度和超連通度的基礎(chǔ)上，深入剖析了交換超立方體網(wǎng)絡(luò)的2-額外點(diǎn)連通度和2-額外邊連通度，證明了當(dāng)t≥s≥2時(shí)，k2(EH(s,t))=3s-2；當(dāng)t≥s≥3時(shí)，λ2(EH(s,t))=3s-1。最后，分析說(shuō)明了在評(píng)價(jià)交換超立方體互連網(wǎng)絡(luò)的可靠性時(shí)，2-額外連通度比傳統(tǒng)連通度更精確、更符合實(shí)際情況。

2 預(yù)備知識(shí)

本文中沒(méi)有定義的理論術(shù)語(yǔ)與符號(hào)描述，本文將參照文獻(xiàn)[22]中的相關(guān)定義。在無(wú)向圖G中，V(G), E(G)分別表示圖G的頂點(diǎn)集和邊集。對(duì)于圖G中的任意的集合F，令G-F表示圖G在移除了F中所有元素之后所形成的子圖。|S|表示集合S的基。(u,v)∈E(G)表示G中任意一條邊。NG(u)和EG(u)分別表示頂點(diǎn)u的鄰居結(jié)點(diǎn)集和鄰居邊集，且NG(u)={v∈V(G)|?(u,v)∈E(G)}, EG(u)={(u,v)∈E(G)|?v∈V(G)}。NG(P)和EG(P)分別表示路徑P在圖G中的鄰居結(jié)點(diǎn)集和鄰居邊集，且NG(P)=(∪?u∈V(P)NG(u))-V(P),EG(P)=(∪u∈V(P)?EG(u))-E(P)。

定義1[17]交換超立方體被定義為一個(gè)無(wú)向圖EH(s,t)=(V,E)(s≥1,t≥1)。頂點(diǎn)集V={as-1…a0bt-1…b0c|ai,bj∈{0,1}且i∈[0,s),j∈[0,t)}。該類超立方體包含3種類型的邊E1, E2和E3，描述為

其中v[x:y]表示v的第y位與第x位之間的比特串，H(v1,v2)表示頂點(diǎn)v1,v2之間的海明距離。圖1示出了兩個(gè)交換超立方體EH(1,1)和EH(1,2)。

引理 1[17]EH(,)st同構(gòu)于EH(,)ts。

引理 2[17]EH(,)st可分解為同構(gòu)于EH(1,)st-或EH(,1)st-的兩個(gè)子圖。

根據(jù)引理1，本文只討論當(dāng)st≤時(shí)EH(,)st的情況，為了研究需要，將EH(,)st分解成子圖L和R，其中

圖1 兩個(gè)交換超立方體EH(1,1)和EH(1,2)

由定義1可知，EH(,)st是在超立方體的基礎(chǔ)上通過(guò)系統(tǒng)地移除部分邊而得到。因此，它是超立方體的一個(gè)生成子圖，保留了其大量?jī)?yōu)越屬性。

引理 3 在EH(,)st中，任意兩個(gè)不相鄰頂點(diǎn)的公共鄰居最多是2。

定理 1 若P為EH(,)st中任意一條長(zhǎng)度為2的路，則NEH(s,t)(P)≥3s-2。

證明 由定義1及引理3，很容易證明NEH(s,t)(P)≥3s-2。 證畢

定理 2 若P為EH(s,t)中任意一條長(zhǎng)度為2的路，則EEH(s,t)(P)≥3s-1。

證明 由定義1中邊的特性，很容易證明EEH(s,t)(P)≥3s-1。 證畢

3 交換超立方網(wǎng)絡(luò)的額外連通度

3.1 刪除部分結(jié)點(diǎn)(邊)的stEH(,)的連通性

在交換超立方網(wǎng)絡(luò)的運(yùn)行中，出現(xiàn)故障結(jié)點(diǎn)和失效鏈路是不可避免的，存在故障結(jié)點(diǎn)和失效鏈路的交換超立方網(wǎng)絡(luò)仍能保持通信是網(wǎng)絡(luò)分析中重要考慮的問(wèn)題之一。下面本文考慮刪除部分結(jié)點(diǎn)(邊)后，交換超立方網(wǎng)絡(luò)的連通性問(wèn)題。

定理 3 對(duì)于任意的F?V(EH(s,t ))且|F|≤3s-3，令Fl=F∩V(L), Fr=F∩V(R)。若在EH(s, t)-F中既無(wú)孤立頂點(diǎn)也無(wú)孤立邊，則R-Fr(或L-Fl)中每一個(gè)頂點(diǎn)均與L-Fl(或R-Fr)中一個(gè)頂點(diǎn)連接。

證明 對(duì)于任意的頂點(diǎn)ur∈V(R-Fr), ur= 1as-2…a0bt-1…b0c ，分以下兩種情形進(jìn)行討論。

(1)令ur=1as-2…a0bt-1…b00。若ul=0as-2…a0bt-1…b00?F ，則定理得證。否則ul∈F。如果存在ur0=1as-2…a0bt-1…b01?F ,1as-2…a0bt-1…且，那么從ur出發(fā)總存在一條路徑使其連接至L-Fl，定理得證。否則ur0∈F。如果且uri(s+t)=0as-2，則定理得證。否則uri與 uri(s+t)(0≤i≤s -2)中至少一個(gè)頂點(diǎn)在F中，此時(shí)令A(yù)={uri,uri(s+t)|0≤i≤s-2}∩F ，則必有|A|≥s-1。

因?yàn)镋H(s,t)-F中不存在孤立點(diǎn)，不妨令vr=，如此(ur,vr)∈E(R-Fr)。若，則定理得證。否則vl∈F。如果存在且b00?F，那么從ur出發(fā)經(jīng)過(guò)vr，總存在一條路徑使其連接至L-Fl。 否則vr0∈F。如果vrj=1as-2…且，則定理得證。否則其中之一必在F中，此時(shí)令B={vrj,vrj(s+t)|0≤j≤s-2且j≠i}∩F，則|B|≥s-2。

令C={wrk,wrk(s+t)|0≤k≤s-2,k≠i,j }, D= {ul,vl,wl,ur0,vr0,wr0}，其中wl∈F, wr0∈F。由于而在C中有s-3對(duì)頂點(diǎn)使ur連接至L-Fl，因此至少存在一個(gè)常數(shù)k(k≠i,j)使u與L-Fl中一個(gè)頂點(diǎn)相連接，定理得證。

(2)令ur=1as-2…a0bt-1…b01。由于N(ur)∩V(L) =φ若，則存在一條路徑，使ur連通至L-Fl。否則u′∈F。令，若|A′|＜t，則必定存在某一i′使1as-2…a0bt-1…bi′…b01b00?F，如此ur連通至L-Fl。否則|A′|≥t。因?yàn)镋H(,)stF-中不存在孤立點(diǎn)，不妨令，如此(ur,)∈E(EH(s,t)-F)。若，則ur連通至L-Fl。否則v′∈F。令j′≤t-1,j′≠i′}∩F ，若|B′|＜t-1，同理可得ur連通至L-Fl。否則，令|B′|≥t-1。

…bi′…bj′…b0；或w′→1a…ab…bi′…bj′

0

輕量級(jí)、大眾化 原生應(yīng)用是專門(mén)針對(duì)某一類移動(dòng)設(shè)備而開(kāi)發(fā)的，下載并安裝到設(shè)備里進(jìn)行使用；輕量級(jí)應(yīng)用是指基于微信等應(yīng)用軟件，以一定形式為用戶提供的應(yīng)用服務(wù)，具有上手容易、發(fā)展迅速的特點(diǎn)[3]。教師采用輕量級(jí)形式的全民學(xué)習(xí)共享平臺(tái)，花費(fèi)更多心思在教學(xué)設(shè)計(jì)上，深耕教學(xué)內(nèi)容，打磨出高品質(zhì)的智慧課堂。教師可以零成本地開(kāi)發(fā)課程資源，對(duì)制作好的PPT添加語(yǔ)音講解，引入學(xué)生投票、提問(wèn)、評(píng)論功能，促使學(xué)生更加專注。教師可以登錄微信完成課件的移動(dòng)查閱、實(shí)時(shí)推送，可以通過(guò)雨課堂或微信群的形式建立立體交流、互動(dòng)互助的共享空間，又能實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)的個(gè)人交流空間。

令C′={u′,v′}，由于|F-(A′∪B′∪C′)|≤(3s-3)-t-(t-1)-2≤s -4，而ur通過(guò)可構(gòu)造t-1條路徑且t-1≥s-1＞s-4，如此至少存在一條路徑使ur與L-Fl中的一個(gè)頂點(diǎn)相連接，定理得證。

定理4 對(duì)于任意的F′?E(EH(s,t ))且|F′|≤3s -2，令=F′∩E(L),=F′∩E(R),=F′∩M0。若在EH(s,t)-F′中既無(wú)孤立頂點(diǎn)也無(wú)孤立邊，則中每一個(gè)頂點(diǎn)均與中一個(gè)頂點(diǎn)相連。

證明 設(shè)ur為R-F中任意一頂點(diǎn)，令ur= 1as-2…a0bt-1…b00，則有以下兩種情形。

(1)令ur=1as-2…a0bt-1…b00。 若es+t(ur)= (ul,ur)?F′，則定理得證。否則es+t(ur)∈F′。若且?F′，則存在一條路徑使ur連通至L-，定理得證。否則e0(ur)∈F′。令A(yù)={ei(ur),es+t(uri)|0≤i≤s-2}∩F′，若|A|＜s-1，則必定存在某一i，使ei(ur)?F′且es+t(uri)?F′，如此ur必定與L-中某一頂點(diǎn)相連接，定理得證。否則|A|≥s-1。

由于EH(s,t)-F′中無(wú)孤立頂點(diǎn)，如此存在某一ei(ur)?F′使(ur,uri)∈E(EH(s,t)-F′)。若es+t(uri)?F′，則定理得證。否則es+t(uri)∈F′。若e0(uri)?F′，此時(shí)可以形成一條通向L-Fl′的路徑為：

如此定理可證。否則e0(uri)∈F′。令B={ej(uri), es+t(urij)|0≤j≤s-2,j≠i}∩F′，若|B|＜s-2，則必定存在某一j，使ej(uri)?F′,es+t(urij)?F′, ur可通過(guò)一條路徑連接至L-，定理可證。否則|B|≥s-2。

由于EH(s,t)-F′中不存在孤立邊，因此存在ej(uri)?F′且j≠i，如此ur經(jīng)過(guò)urij至L-可構(gòu)造如下路徑：

或ek(urij)→es+t(urijk)，其中0≤k≤s-2且 k≠i,j。

令C={es+t(ur),e0(ur),es+t(uri),e0(uri)}，因?yàn)閨F′-A∪B∪C|=|F′|-|A|-|B|-|C|≤(3s -2) -(s-1)-(s-2)-4=s-3，而ur通過(guò)urij可構(gòu)造(s-1)條通向L-的路徑，如此至少存在一條路徑使ur與L-中一個(gè)頂點(diǎn)相連，定理得證。

(2) 令ur=1as-2…a0bt-1…b01。 由于N(ur)∩V(L)=φ，若e0(ur)F′，則此時(shí)存在一條路徑ur→ur0→0as-2…a0bt-1…b00，定理得證。否則e0(ur)∈F′。令≤t-1}∩F′，若|A′|＜t，則同理可得存在某一i′，使，如此ur可連接至L-Fl′中一個(gè)頂點(diǎn)，定理可證。否則|A′|≥t。

，同理通過(guò)uri′j′可構(gòu)造通向的路徑為：

uri′j′→，其中0≤k′≤t-1且k′≠i′,j′。

令C′={e0(ur),e0(uri′)}，由于|F′-A′∪B′∪C′|≤(3s-2)-t-(t-1)-2≤s -3,而ur通過(guò)uri′j′可構(gòu)造(t-1)條通向L-的路徑，其中t≥s，因此至少存在一條路徑使ur與L-中一個(gè)頂點(diǎn)相連，定理得證。

3.2 stEH(,)的2-額外連通度

額外連通度是評(píng)價(jià)交換超立方網(wǎng)絡(luò)可靠性的重要度量，依靠于3.1節(jié)的結(jié)論，下面給出交換超立方網(wǎng)絡(luò)的2-額外連通度的相關(guān)結(jié)果。

引理 4[19]當(dāng)s≤t時(shí)，k′(EH(s,t))=λ′(EH(s,t)) =2s。定理 5 k2(EH(s,t))=3s-2，其中t≥s≥2。證明 在EH(s,t)中任取一條長(zhǎng)度為2的路徑P，由定理1有NEH(s,t)(P)≥3s-2。很容易驗(yàn)證，EH(s,t)-NEH(s,t)(P)既不包含孤立頂點(diǎn)，也不包含孤立邊，如此NEH(s,t)(P)為一點(diǎn)割集且k2(EH(s,t))≤3s-2。若要證明定理5成立，只需證明k2(EH(s,t))≥3s-2，即證明對(duì)于任意的頂點(diǎn)集F?V(EH(s,t))，當(dāng)|F|=3s-3且不存在孤立頂點(diǎn)也不存在孤立邊時(shí)，EH(s,t)-F是連通的。令Fl=F∩V(L), Fr=F∩V(R)，由定理3可知，R-Fr中任意一頂點(diǎn)與L-Fl中一頂點(diǎn)連通。如此，只需證明當(dāng)|F|=3s-3且在EH(s,t)-F不存在孤立頂點(diǎn)也不存在孤立邊時(shí)，L-Fl是連通的即可。不失一般性，令|Fl|≤|Fr|，則|Fl|≤(3s-3) /2＜2s-2(s≥2)。

若在L-Fl中無(wú)孤立點(diǎn)，而|Fl|＜2s-2= k′(L)，則L-Fl是連通的，定理得證。否則在L-Fl中有孤立點(diǎn)，假設(shè)有兩個(gè)孤立點(diǎn)，記為x,y。由于|NL(x)|,|NL(y)|≥(s-1)+1=s ，且在L中任意兩個(gè)不相鄰頂點(diǎn)之間的公共鄰居最多為2，故至少移出(2s-2)個(gè)頂點(diǎn)才能得到兩個(gè)孤立點(diǎn)，而|Fl|＜2s-2，如此在L中只存在一個(gè)孤立點(diǎn)，設(shè)為ul，即NL(ul)?Fl且|NL(ul)|≥s。下面證明當(dāng)|F|=3s-3且在EH(s,t)-F不存在孤立頂點(diǎn)也不存在孤立邊時(shí)，ul與L-Fl∪{ul}是連通的。

若 ul=0as-2…a0bt-1…b01時(shí)，由于N(ul)∩V(R) =φ，則ul在EH(s,t)-F中為一孤立點(diǎn)，這與EH(s,t)-F不存在孤立頂點(diǎn)相矛盾，此時(shí)ul只能取下面的值，即 ul=0as-2…a0bt-1…b00。

因?yàn)樵贓H(s,t)-F中無(wú)孤立點(diǎn)，故存在ur= 1as-2…a0bt-1…b00?F ，如此(ul,ur)∈E(EH(s,t ) -F)。若ur0=1as-2…a0bt-1…b01?F , 1as-2…a0bt-10as-2…a0bt-1…bi′…b00?F ，則定理得證。否則且則定理得證。否則令A(yù)={uri,uri(s+t)|0≤i≤s-2}∩F，則|A|≥s-1。

因?yàn)樵贓H(s,t)-F中無(wú)孤立邊，如此存在一個(gè)uriF，使(ur,uri)∈E(EH(s,t)-F)，則ul通過(guò)uri構(gòu)造通向L-ul的路徑為：

uri→，其中0≤j≤ s-2且j≠i。

由于|F-NL(ul)∪A∪{ur0}|≤(3s-3)-s-(s -1)-1=s-3且ul通過(guò)uri可構(gòu)造(s-2)+1= s-1條通向L-ul的路徑，故至少存在一條路徑使ul與L-Fl∪{ul}連通，定理得證。

引理5[22]對(duì)任意的圖G，都有k(G)≤λ(G)≤δ(G)。

引理 6[18]當(dāng)s≤t時(shí)，k(EH(s,t))=λ(EH(s,t)) =s +1。

定理 6 λ2(EH(s,t))=3s -1，其中t≥s≥3。

證明 在EH(s,t)中任取一條長(zhǎng)度為2的路徑P，根據(jù)定理2有|EEH(s,t)(P)|≥3s-1。由于EH(s,t)- EEH(s,t)(P)既不包含孤立頂點(diǎn)也不包含孤立邊，根據(jù)λ2的定義，有λ2(EH(s,t))≤3s-1。如此，只需證明λ2(EH(s,t))≥3s-1，即證明對(duì)于任意的邊集F′?E(EH(s,t ))，若|F′|=3s-2且既無(wú)孤立頂點(diǎn)也無(wú)孤立邊時(shí)，EH(s,t)-F′為連通的。令=F∩E(L),=F∩E(R),=F∩M0。由定理4可知，R-中每個(gè)頂點(diǎn)至少與L-中一個(gè)頂點(diǎn)相連接，故只需證明當(dāng)|F′|=3s-2且EH(s,t)-F′既無(wú)孤立頂點(diǎn)也無(wú)孤立邊時(shí)，L-是連通的即可。由于|F′|=3s-2＜4(s -1)(s≥3)，故中至少兩個(gè)小于2(s-1)，不妨設(shè)||＜ 2(s-1)。若L-中無(wú)孤立點(diǎn)，且||＜2(s-1) =λ′(L) ，如此L-為連通的，定理得證。否則存在孤立點(diǎn)。同理定理5可得，L-中沒(méi)有兩個(gè)孤立點(diǎn)，只能有一個(gè)孤立點(diǎn)，記為ul，此時(shí)有EL(ul)?且|EL(ul)|≥s。由于λ(L-ul)≥k(L而＜s-2＜s -1，如此為連通的。下面只需證明當(dāng)|F′|=3s-2且在EH(s,t)-F′中既不包含孤立點(diǎn)也不包含孤立邊時(shí)，ul與L-∪{ul}連通即可。

若ul=0as-2…a0bt-1…b01，由于ul在L-中為孤立點(diǎn)且N(ul)∩V(R)=φ，這與E(EH(s,t)-F′)中無(wú)孤立頂點(diǎn)相矛盾，如此ul只能為下面值，即ul=0as-2…a0bt-1…b00。

由于EH(s,t)-F′中無(wú)孤立點(diǎn)，如此es+t(ul)?F′，使(ul,ur)∈E(EH(s,t)-F′)，其中us+t=ur。若e0(ur)?F′，則ul可通過(guò)下面路徑連接至L-∪{ul}：

如此，則定理成立。否則e0(ur)∈F′，令A(yù)′= {ei(ur),es+t(uri)|0≤i≤s-2}∩F′，則|A′|≥s-1。

由于EH(s,t)-F′中無(wú)孤立邊，則存在某個(gè)i，使ei(ur)F′，如此(ur,uri)∈E(EH(s,t)-F′)，則從ul出發(fā)經(jīng)過(guò)uri可構(gòu)造通向L-ul的路徑為：

ul→ur→uri→或ul→ ur→其中0≤j≤s -2且j≠i。

由于|F′-A′∪EL(ul)∪{e0(ur)}|=|F′|-|A′| -|EL(ul)|-1≤s -2，而ul通過(guò)uri連接至L-ul的路徑有1s-條，故至少存在一條路徑使lu連接至

4 stEH(,)的2-額外連通度與傳統(tǒng)連通度比較

綜上所述，當(dāng)t≥s≥2時(shí)，EH(s,t)的2-額外點(diǎn)連通度是3s-2；當(dāng)t≥s≥3時(shí)，EH(s,t)的2-額外邊連通度是3s-1。而當(dāng)t≥s時(shí)，EH(s,t)的傳統(tǒng)點(diǎn)連通度和傳統(tǒng)邊連通度均是s+1。由此可以看出，2-額外連通度幾乎是傳統(tǒng)連通度的3倍，這使得交換超立方體網(wǎng)絡(luò)可靠性的量度更加精確，因此2-額外連通度比傳統(tǒng)連通度更適合評(píng)價(jià)大規(guī)模交換超立方體網(wǎng)絡(luò)的可靠性。另一方面，傳統(tǒng)連通度假定交換超立方體網(wǎng)絡(luò)的任一節(jié)點(diǎn)或任一鏈路的所有鄰居節(jié)點(diǎn)(或鄰居鏈路)都可能同時(shí)故障，這種情況發(fā)生的概率是2n/＜10-6(當(dāng)n≥6時(shí))，不切實(shí)際。而2-額外連通度假定交換超立方體網(wǎng)絡(luò)的任一節(jié)點(diǎn)或任一鏈路的部分鄰居節(jié)點(diǎn)(或鄰居鏈路)不能同時(shí)故障，這更符合實(shí)際情況，因此在評(píng)價(jià)交換超立方體互連網(wǎng)絡(luò)的可靠性時(shí)，2-額外連通度比傳統(tǒng)連通度更具優(yōu)勢(shì)性。

5 結(jié)束語(yǔ)

本文在交換超立方體網(wǎng)絡(luò)傳統(tǒng)連通度和超連通度的基礎(chǔ)上深入研究，進(jìn)一步證明了2-額外點(diǎn)連通度和2-額外邊連通度：當(dāng)t≥s≥2時(shí)，k2(EH(s,t))= 3s-2；當(dāng)t≥s≥3時(shí)，λ2(EH(s,t))=3s -1。也就是說(shuō)，當(dāng)t≥s≥2(或t≥s≥3)時(shí)，交換超立方體至少刪除3s-2個(gè)頂點(diǎn)(或3s-1條邊)，才能得到既不包含孤立頂點(diǎn)也不包含孤立邊的非連通圖。該結(jié)果的得出進(jìn)一步擴(kuò)展了交換超立方體網(wǎng)絡(luò)的可靠性研究，同時(shí)對(duì)交換超立方體網(wǎng)絡(luò)的可靠性提供了更精確的量度。

[1] Harary F. Conditional connectivity[J]. Networks, 1983, 13(3): 347-357.

[2] Fàbrega J and Fiol M A. Extraconnectivity of graphs with large girth[J]. Discrete Mathematics, 1994, 127(1): 163-170.

[3] Fàbrega J and Fiol M A. On the extraconnectivity of graphs[J]. Discrete Mathematics, 1996, 155(1): 49-57.

[4] Xu J M and Zhu Q. On restricted connectivity and extra-connectivity of hypercubes and folded hypercubes[J]. Journal of Shanghai Jiaotong University, 2005, 10(2): 203-207.

[5] Yang W and Meng J. Extraconnectivity of hypercubes[J]. Applied Mathematics Letters, 2009, 22(6): 887-891.

[6] Zhu Q, Xu J M, Hou X, et al.. On reliability of the folded hypercubes[J]. Information Sciences, 2007, 177(8): 1782-1788.

[7] Hong W S and Hsieh S Y. Extra edge connectivity of hypercube-like networks[J]. International Journal of Parallel, Emergent and Distributed Systems, 2013, 28(2): 123-133.

[8] Li H and Yang W. Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes[J]. Discrete Applied Mathematics, 2013, 161(16/17): 2753-2757. [9] Xu J M, Zhu Q, and Xu M. Fault-tolerant analysis of a class of networks[J]. Information Processing Letters, 2007, 103(6): 222-226.

[10] Zhu Q, Wang X K, and Cheng G. Reliability evaluation of BC networks[J]. IEEE Transactions on Computers, 2013, 62(11): 2337-2340.

[11] Saad Y and Schultz M H. Topological properties of hypercubes[J]. IEEE Transactions on Computers, 1988, 37(7): 867-872.

[12] El-Amawy A and Latifi S. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42.

[13] Fan J X. BC interconnection networks and their properties[J]. Chinese Journal of Computers-Chinese Edition, 2003, 26(1): 84-90.

[14] Cheng B, Fan J, Jia X, et al.. Parallel construction of independent spanning trees and an application in diagnosis on M?bius cubes[J]. Journal of Supercomputing, 2013, 65(3): 1279-1301.

[15] Chen J C, Lai C J, Tsai C H, et al.. A lower bound on the number of Hamiltonian cycles through a prescribed edge in acrossed cube[J]. Applied Mathematics and Computation, 2013, 219(19): 9885-9892.

[16] Yang X F, Evans D J, and Megson G M. The locally twisted cubes[J]. International Journal of Computer Mathematics, 2005, 82(4): 401-413.

[17] Loh P K K, Hsu W J, and Pan Y. The exchanged hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874.

[18] Ma M J. The connectivity of exchanged hypercubes[J]. Discrete Mathematics, Algorithms and Applications, 2010, 2(2): 213-220.

[19] Ma M J and Zhu L Y. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011, 111(8): 360-364.

[20] Li X J and Xu J M. Generalized measures of fault tolerance in exchanged hypercubes[J]. Information Processing Letters, 2013, 113(14): 533-537.

[21] zar Klav∨S and Ma M J. The domination number of exchanged hypercubes[J]. Information Processing Letters, 2014, 114(4): 159-162.

[22] Bondy J A and Murty U S R. Graph Theory with Applications[M]. London: MacMillan, 1976: 10-24.

梁家榮： 男，1966年生，教授，博士，博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)與并行計(jì)算、人工智能.

白 楊： 男，1987年生，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)與并行計(jì)算.

王新陽(yáng)： 男，1985年生，博士生，研究方向?yàn)榫W(wǎng)絡(luò)與并行計(jì)算、云計(jì)算、大數(shù)據(jù).

A New Method Used for Evaluating Reliability of the Exchanged Hypercube Network

Liang Jia-rong①Bai Yang①Wang Xin-yang②

①(School of Computer and Electronic Information, Guangxi University, Nanning 530004, China)
②(School of Computer Science & Engineering, South China University of Technology, Guangzhou 510006, China)

Reliability problems on Exchanged Hypercube interconnection network(EH(s,t)) regard as one of important candidates of network models in large-scale processor systems are concerned by people. The extra connectivity, which is an important measure in evaluating the reliability, is utilized to analyze the reliability of exchanged hypercube interconnection network. Then the 2-extra vertex connectivity(k2(EH(s,t)))and 2-extra edge connectivity(λ2(EH(s,t )))of exchanged hypercube interconnection network are obtained. The conclusions are thatk2(EH(s,t))=3s-2 fort≥s≥2; andλ2(EH(s,t))=3s -1 fort≥s≥3. The analysis shows that the 2-extra connectivity is much superior to the traditional connectivity in evaluating the reliability of exchanged hypercube interconnection network.

Interconnection network; Exchanged hypercube; Reliability; Extra connectivity

TP393

A

1009-5896(2015)03-0693-07

10.11999/JEIT140557

2014-04-28收到，2014-07-14改回

國(guó)家自然科學(xué)基金(61363002)資助課題

*通信作者：梁家榮 gxuliangjr@163.com