BC網(wǎng)絡(luò)的限制邊連通度

王玉潔，原 軍，劉秀麗，高曉慧

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

?

BC網(wǎng)絡(luò)的限制邊連通度

王玉潔，原 軍，劉秀麗，高曉慧

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

互連網(wǎng)絡(luò)的可靠性評估對于多處理系統(tǒng)的設(shè)計和維護(hù)是非常重要的。限制邊連通度是互連網(wǎng)絡(luò)可靠性評估的一個重要參數(shù)，因此，研究限制邊連通度對互聯(lián)網(wǎng)絡(luò)的可靠性評估具有重要意義。通過研究n-維雙射連通互連網(wǎng)絡(luò)(簡稱BC網(wǎng)絡(luò))的h-限制邊連通度的性質(zhì)，可推導(dǎo)得到n-維BC網(wǎng)絡(luò)的h-限制邊連通度的值。另外，因為BC網(wǎng)絡(luò)包含若干著名的網(wǎng)絡(luò)模型，比如，超立方體、莫比烏斯立方體、交叉立方體、扭立方體、生成扭立方體、廣義扭立方體和M立方體，所以，應(yīng)用推導(dǎo)得到的結(jié)果可以得出這些網(wǎng)絡(luò)的h-限制邊連通度。

BC網(wǎng)絡(luò)；可靠性；限制邊連通度；互連網(wǎng)絡(luò)

眾所周知，邊連通度是反映圖的連通性質(zhì)的一個重要參數(shù)[1]，而要更精確地刻畫圖的連通性質(zhì)，經(jīng)典邊連通度存在著不足之處。為克服其缺陷，在文獻(xiàn)[2]中引入了限制邊連通度。限制邊連通度是度量大型互連網(wǎng)絡(luò)可靠性的一類重要參數(shù)。本文主要探究雙射連通網(wǎng)絡(luò)的限制邊連通度。

雙射連通網(wǎng)絡(luò)(簡稱BC網(wǎng)絡(luò))是以立方體為背景的一系列網(wǎng)絡(luò)，它包含許多著名的網(wǎng)絡(luò)，如，超立方體、莫比烏斯立方體[2]、扭立方體[3]、交叉立方體[4]、生成扭立方體[5]、廣義扭立方體[6]和立方體[7]。研究BC網(wǎng)絡(luò)的性質(zhì)，則可獲得以上各種變形網(wǎng)絡(luò)的性質(zhì)。

1 預(yù)備工作和術(shù)語

設(shè)G=(V,E)是一個無向圖，其中V=V(G)，E=E(G)分別表示圖G的頂點集和邊集。假設(shè)V′是V的一個非空子集，以V′為頂點集，以兩端點均在V′中的邊的全體為邊集所組成的子圖，稱為G的由V′導(dǎo)出的子圖，記為G[V′].G的一條途徑是指一個有限非空序列w=v0e1v1e2v2…ekvk，它的項交替地為頂點和邊，使得ei(1≤i≤k)的端點為vi-1和vi，則稱w是一條(v0,vk)途徑。若途徑w的頂點v0,v1,…,vk互不相同，則w稱為路。G的兩個頂點u和v稱為連通的，如果在G中存(u,v)在路。

對于一個連通圖G,F是G的一個邊子集，若G-F不連通且G-F的每個分支至少有h個頂點，則稱F為G的h-限制邊割，記為λh-邊割。G的最小λh-邊割所含邊數(shù)稱為G的h-限制邊連通度，記為λh(G).

定義1 一維BC圖B1是只有兩個頂點的完全圖。一維BC圖的類記為B1={B1}.一個圖G是n-維BC圖，記為Bn，若存在V0,V1?V(G)滿足如下兩個條件：

(1)V(G)=V0∪V1,V0≠?,V1≠?,V0∩V1=?,G[V0],G[V1]∈Bn-1；

(2)V0和V1之間的邊集形成G的一個完美對集M.

n-維雙射連通圖Bn是n正則的，有2n個頂點和n2n-1條邊。n-維BC圖的集合稱為它的類，記為Bn.為了具體討論BC圖，記V(Bn)為=X1X2…Xn={x1x2…xn∶xi∈{1,0},i=1,2,…,n}(事實上，這種表示方法與超立方體的表示類似)。因此，定義1中的V0和V1可分別表示為X1X2…Xn-10和X1X2…Xn-11.類似地，用X1X2…Xkzk-1…zn={x1x2…xkzk+1…zn∶xi∈{1,0},i=1,2,…,k,zj是固定的，j=k+1,…n}來表示Bn中的k-維BC子圖。超立方體、扭立方體、交叉立方體、莫比烏斯立方體、生成扭立方體等都是對以上結(jié)論的應(yīng)用，因此，此處省略了這些圖的具體定義，只給出一些圖(見圖1-2)，這些圖將會呈現(xiàn)出將要使用的結(jié)構(gòu)性質(zhì)。

圖1 Q4(左)和CQ4(右)Fig.1 Q4(left)and CQ4(right)

圖2 TQ4(左)和LTQ4(右)Fig.2 TQ4(left)and LTQ4(right)

2 主要結(jié)果

近年來，Zhang Mingzu，Meng Jixiang和Yang Weihua[13]等證得了以下結(jié)論。

引理2 若0≤q≤2c，則exq≤cq.

另外，由λh(Bn)和ξm(Bn)的定義，有λh(Bn)=min{ξm(Bn)∶h≤m≤2n-1}.

情況1 討論exh-exh-1≤n.

情況2 討論exh-1-exh-2≤n.

情況3 討論exh-2-exh-3≤n.

情況4 討論exh-3-exh-4≤n.類似情況3的討論方法，可得exh-3-exh-4≤n.

綜上，則有exh-exh-4=(exh-exh-1)+(exh-1-exh-2)+(exh-2-exh-1)+(exh-3-exh-4)≤4n.證畢。

證明：由引理4，得ξh(Bn)-ξh-4(Bn)=nh-exh-n(h-4)-exh-4=4n-(exh-exh-4)≥4n-4n=0.因此ξh(Bn)=nh-exh關(guān)于h是不減的。證畢。

證明：分兩種情況證明：

證明：引理7的直接推論。證畢。

證明：當(dāng)2≤c≤n-4時，因為2c+2≤h≤2c+1+2，所以設(shè)h=2c+2+p,(0≤p≤2c).由引理9，得exh=ex2c+2+exp+4p.又由引理2，exp≤cp.則有ξh(Bn)-ξ2c+2(Bn)=nh-exh-n(2c+2)+ex2c+2=np-(exp+4p)=(n-4)p-exp≥(n-4)p-cp=(n-4-c)p≥0.證畢。

證明：結(jié)合引理7與引理10即可證。證畢。

證明：引理11的直接推論。證畢。

事實上，由引理11容易看出，ξh(Bn)的單調(diào)性走勢是上升的。當(dāng)h無限變大時，ξh(Bn)也將變大，即ξh(Bn)≥ξR-2(Bn)是成立的，也就是下面的觀察13成立。

觀察13 當(dāng)b≥n-4時，若2b-2≤h<2n-1，易知，ξh(Bn)≥ξR-2(Bn).

下證λh(Bn)≥nh-exh.假設(shè)F為最小的λh-邊割，且C為階為m的較小分支(Bn-F至少含有2個分支)。分兩種情況證明：

(1) 首先假設(shè)2≤hξh.若k≤m≤R-2，由引理6可知，ξm≥ξR-2=ξK.又2≤h

(2)當(dāng)K

由于BC網(wǎng)絡(luò)包含Qn、MQn、TQn、CQn、LTQn、GTQn和MCQn.故研究BC網(wǎng)絡(luò)的性質(zhì)，則可獲得以上超立方體的變形網(wǎng)絡(luò)的性質(zhì)，也就是下面的推論15成立。

[1] 段晉芳，原軍.二部圖2等周邊連通度最優(yōu)的充分條件[J].太原科技大學(xué)學(xué)報，2010，31(4)：309-311.

[2]CULLP.Thecubes[J].IEEETransactionsonComputers，1995，44：647-659.

[3]HIBERSPAJ，KOOPMANMRJ，SNEPSCHEUTJVD.Thetwistedcube[C]∥ProceedingsoftheConferenceonParallelArchitecturesandLanguagesEurope，LectureNotesinComputerScience，Europe，1987：152-159.

[4]EFEK.Avariationonthehypercubewithlowerdiameter[J].IEEETransactionsoncomputers，1991，40(11)：1312-1316.

[5]YANGXF，EVANSDJ，MEGSONGM.Thelocallytwistedcubes[J].IntJComputMath.2005，82(4)：401-413.

[6]CHEDIDFB.Onthegeneralizedtwistedcube[J].InformationProcessingLetters，1995，55(1)：49-52.

[7]SINGHVINK，GHOSEK.TheMcube：asymmetricalcubebasednetworkwithtwistedlinks[C]∥Proceedingsofthe9thIEEEInternationalParallelProcessingSymposium，SantaBarbara，CA，1995：11-16.

[8]CHENYC，TANJJM，HSULH，KAOSS.Super-connectivityandsuperedge-connectivityforsomeinterconnectionnetworks[J].AppliedMathematicsandComputation，2003，140：245-254.

[9]ZHUQ，XUJM.Onrestrictededgeconnectivityandextraedgeconnectivityofhypercubesandfoldedhypercubes[J].JUnivSciTechnolChina，2006，36：246-253.

[10]ZHUQ，XUJ，HOUX，XUM.Onreliabilityofthefoldedhypercubes[J].InformationScience，2007，177：1782-1788.

[11]ZHUQ，XUJ，LVM.Edgefaulttoleranceanalysisofaclassofinterconnectionnetworks[J].MathematicsandComputation，2006，172：111-121.

[12]YANGW，LINH.ReliabilityevaluationofBCnetworksintermsofextravertex-andedge-connectivity[J].IEEETransactionsonComputers，2014，63(10)：2540-2548.

[13]ZHANGM，MENGJ，YANGW，TIANY.Reliabilityanalysisofbijectiveconnectionnetworksintermsoftheextraedge-connectivity[J].InformationScience，2014，279：374-382.

Reliability Evaluation of BC Networks in Terms of the Extra Edge-connectivity

WANG Yu-jie，YUAN Jun，LIU Xiu-li ，GAO Xiao-hui

(School of Applied Sciences，Taiyuan University of Science and Technology，Taiyuan 030024)

Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems.The restricted edge-connectivity is an important parameter for the reliability evaluation of interconnection network.Therefore，the study on the restricted edge-connectivity is of great significance to the reliability evaluation of interconnection network.We obtain the value ofh-extra edge-connectivity by researching the properties ofh-extra edge-connectivity of ann-dimensional bijective connection network (in brief，BC network).Besides，since the BC network includes several well-known network models，such as hypercubes，M?bius cubes，crossed cubes，twisted cubes，locally-twisted cubes，generalized twisted cubes andMcubes，so the application of our results can be launched theh-extra edge-connectivity of these networks.

BC network，reliability，extra edge-connectivity，interconnection network

2015-04-17

國家青年科學(xué)基金(61402317)；國家數(shù)學(xué)天元基金(11126076)；山西省青年自然科學(xué)基金(2012021001-2)

王玉潔(1986-)，女，碩士研究生，主要研究方向為圖論及泛函分析。

1673-2057(2015)06-0480-06

O157.5

A

10.3969/j.issn.1673-2057.2015.06.014