蔡學(xué)鵬, 馬 麗

(新疆農(nóng)業(yè)大學(xué) 數(shù)理學(xué)院,新疆 烏魯木齊 830052)

引言

眾所周知,互連網(wǎng)絡(luò)在并行計(jì)算及通信系統(tǒng)中發(fā)揮著重要作用。一個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在數(shù)學(xué)上通常被抽象的模型化為一個(gè)圖G=(V(G),E(G)),其中V(G)是圖G的頂點(diǎn)集來表示網(wǎng)絡(luò)處理器的集合,E(G)是圖G的邊集來表示網(wǎng)絡(luò)的通信鏈路集。在本文中,術(shù)語圖和網(wǎng)絡(luò)可以互換使用。本文中所有的圖都認(rèn)為是無向的,簡單的和連通的,對(duì)于未說明的圖論符號(hào)和術(shù)語,可參考文獻(xiàn)[1-2]。

設(shè)G=G(V,E)是一個(gè)圖，對(duì)于圖G中兩個(gè)子圖H和K，記G-H是點(diǎn)集V(G)-V(H)誘導(dǎo)的子圖。設(shè)NH(K)是在H中且與K中的點(diǎn)相鄰的點(diǎn)的集合，特殊地，如果K={v}，可記作NH(v)。設(shè)dG(v)=|NG(v)|是點(diǎn)v在圖G中的度，設(shè)NG[v]=NG(v)∪{v}。如果不產(chǎn)生歧義，我們可省略下標(biāo)即記為d(v),N(v),N[v]。δ(G)=min {d(v)|v∈V(G)}表示圖G的最小度。圖G的最小邊度定義為ξ(G)=min{d(u)+d(v)-2|(u,v)∈E(G)}。

圖G的經(jīng)典連通度κ(G)和邊連通度λ(G)是衡量網(wǎng)絡(luò)可靠性和容錯(cuò)性的兩個(gè)重要參數(shù)[3-4]。連通度κ(G)和邊連通度λ(G)越大,網(wǎng)絡(luò)的可靠性就越高。但是,這兩個(gè)參數(shù)有明顯的不足之處,比如,在互連網(wǎng)絡(luò)的實(shí)際應(yīng)用當(dāng)中,與一個(gè)處理器相連接的所有處理器(鏈路)同時(shí)發(fā)生故障可能性較低,所以這兩個(gè)參數(shù)衡量網(wǎng)絡(luò)可靠性和容錯(cuò)性是不精確的。為克服這些不足之處,Esfahanian在文獻(xiàn)[5]中提出了超連通度(超邊連通度)的概念,超連通度(超邊連通度)比連通度(邊連通度)能更好地衡量網(wǎng)絡(luò)可靠性和容錯(cuò)性。

設(shè)S?V(G)(S?E(G))，如果圖G-S不是連通的,并且毎個(gè)分支都至少包含兩個(gè)頂點(diǎn),則稱S是G的一個(gè)超點(diǎn)割(超邊割)。若圖G存在超點(diǎn)割(超邊割),則G的所有超點(diǎn)割(超邊割)中基數(shù)最小的超點(diǎn)割(超邊割)的基數(shù)稱為G的超連通度(超邊連通度),記為κ(1)(G)(λ(1)(G))。超連通度(超邊連通度)已經(jīng)在許多互連網(wǎng)絡(luò)(圖)中得到了研究,見參考文獻(xiàn)[6-12]。

在平行計(jì)算系統(tǒng)中，n維超立方體Qn[13-14],n維折疊超立方體FQn[15]和交叉超立方體EH(s,t)[16]是三個(gè)重要的互連網(wǎng)絡(luò)?；谶@三個(gè)網(wǎng)絡(luò)，李等人在2005年[17]提出了一個(gè)新的網(wǎng)絡(luò)交換折疊超立方體EFH(s,t)。EFH(s,t)是在EH(s,t)的基礎(chǔ)上增加了一些額外的邊獲得的并且這些邊稱為補(bǔ)邊，交換折疊超立方體有許多重要的特性，比如它有短的直徑和低消費(fèi)因子。最近Bhavani[18]等人研究了交換折疊超立方體的短路徑問題。

Esfahanian在文獻(xiàn)[5]中、馬明杰在文獻(xiàn)[8]中、徐俊明在文獻(xiàn)[9]中分別證明了

κ(1)(Qn)=λ(1)(Qn)=2n-2，n≥3;

κ(1)(EHs,t))=λ(1)(EH(s,t))=2s，1≤s≤t;

κ(1)(FQn)=λ(1)(FQn)=2n，n≥4。

我們?cè)谖墨I(xiàn)[10]中證明了κ(1)(FCQn)=λ(1)(FCQn)=2n，n≥4。 本文將探討交換折疊超立方EFH(s,t)的超連通度和超邊連通度,最終確定了κ(1)(EFH(s,t))=λ(1)(EFH(s,t))=2s+2,1≤s≤t。

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

一個(gè)n元二進(jìn)制字符串x=xn-1xn-2…x0的第i個(gè)字符xi記為x[i]，0≤i≤n-1。

稱為x=xn-1xn-2…x0與y=yn-1yn-2…y0的哈明距離。

定義1.1[16]設(shè)交換超立方體EH(s,t)=G(V,E)，s,t是正整數(shù)。交換超立方體的點(diǎn)集V(EH(s,t))={as-1as-2…a1a0bt-1bt-2…b1b0c|ai,bj,c∈{0,1},0≤i≤s-1,0≤j≤t-1}，交換超立方體的邊集E(EH(s,t))={(u,v)| (u,v)∈V(EH(s,t))×V(EH(s,t))}是由三種類型的邊E1,E2,E3構(gòu)成。其中

E1∶u[s+t∶1]=v[s+t∶1],u[0]≠v[0]。

E2∶u[t∶1]=v[t∶1],H(u[s+t∶t+1],v[s+t∶t+1])=1,u[0]=v[0]=0。

E3∶u[s+t∶t+1]=v[s+t∶t+1],H(u[t∶1],v[t∶1])=1,u[0]=v[0]=1。

通過定義1.1，立即可得EH(s,t)的點(diǎn)數(shù)|V(EH(s,t))|=2s+t+1，EH(s,t)的邊數(shù)|E(EH(s,t))|=(s+t+2)2s+t+1，設(shè)任意一條邊(u,v)∈E(EH(s,t))，則存在唯一確定的i∈{0,1,2,3,…,s+t}使得u[i]≠v[i]且u[j]=v[j]，j=1,2…i-1,i+1,…,s+t. 此時(shí)稱邊(u,v)是i-邊。如果EH(s,t)中兩個(gè)點(diǎn)u和v通過i-邊相鄰，則稱u和v沿維數(shù)i相鄰。我們也稱u是v的i-鄰點(diǎn)，記作v=ni(u)。因?yàn)镋H(s,t)是Qs+t+1的一個(gè)子圖，所以EH(s,t)是一個(gè)二部圖。

EH(s,t)中從一個(gè)頂點(diǎn)u0出發(fā)的路徑u0→u1→…→un+1可以由唯一的序列w=(i0-i1-i2-…-in)確定，其中ik∈{0,1,…,(s+t)}。即u1是由與u0關(guān)聯(lián)的i0-邊所確定，u2是由與u1關(guān)聯(lián)的i1-邊所確定，依此類推。例如，在EH(2,2)中，如果頂點(diǎn)u0=00000，則由w=(2-0-4)確定的從u0出發(fā)的路徑是00000→00100→00101→10101。

圖1 EH(1,2)和EFH(1,2)

EH(1,2)和EFH(1,2)的圖(見圖1)。

設(shè)u∈V(EFH(1,2)).通過定義1.2，如果u[0]=0，則d(u)=s+2，否則d(u)=t+2。

下面給出EH(s,t)和EFH(s,t)的一些結(jié)論，主要結(jié)果的證明將會(huì)用到這些結(jié)論。

定理1.1[7]κ(EH(s,t))=λ(EH(s,t))=s+1,1≤s≤t。

定理1.2[16]EH(s,t)同構(gòu)與EH(t,s)。

定理1.3[17]EFH(s,t)同構(gòu)與EFH(t,s)。δ(EFH(s,t))=s+1。

通過引理1.2和引理1.3，可以在下面討論中設(shè)s≤t，則δ(EH(s,t))=s+1且δ(EFH(s,t))=s+2。

定理1.4[16]EH(s,t)可分解成兩個(gè)EH(s-1,t)或兩個(gè)EH(s,t-1)。

根據(jù)EFH(s,t)的定義容易得出EFH(s,t)具有下面兩個(gè)性質(zhì)，這兩個(gè)性質(zhì)將會(huì)簡化主要結(jié)果的證明。

性質(zhì)1.5交換折疊超立方體網(wǎng)絡(luò)EFH(s,t)可以分解成兩個(gè)子圖L和R，其中

V(L)={0as-2…a0bt-1…b0c|ai,bj,c∈{0,1},0≤i≤s-2,1≤j≤t-1}

V(R)={1as-2…a0bt-1…b0c|ai,bj,c∈{0,1},0≤i≤s-2,1≤j≤t-1}

L和R分別是由點(diǎn)集V(L)和V(R)誘導(dǎo)的子圖。明顯地，L和R都同構(gòu)于EH(s-1,t)，并且L和R之間的邊是由E2和E4構(gòu)成，記作EFH(s,t)=L⊕R。

性質(zhì)1.6EFH(s,t)可分解成2t個(gè)同構(gòu)于超立方體Qs的不交子圖和2s個(gè)同構(gòu)于超立方體Qt的不交子圖。設(shè)={Li|Li?Qs,1≤i≤2t}且R={Rj|Rj?Qt,1≤j≤2t}

(1)任何兩個(gè)子圖Li與Lm(i≠m)之間是不連邊的；同理Rj與Rn(j≠n)之間也是不連邊的。

(2)子圖Li中的每一個(gè)點(diǎn)u在R中都有的兩個(gè)鄰點(diǎn)且這兩個(gè)鄰點(diǎn)是在不同的子圖Rj中的；同理子圖Rj中的每一個(gè)點(diǎn)u在中都有的兩個(gè)鄰點(diǎn)且這兩個(gè)鄰點(diǎn)是在不同的子圖Li中的。

(3)Li中不同的點(diǎn)在R中的鄰點(diǎn)都位于不同的子圖Rj中；同理Rj中不同的點(diǎn)在中的鄰點(diǎn)都位于不同的子圖Li中。

文獻(xiàn)[8]中，作者證明了折疊超立方體FQn(n≥4)中不含3圈，并且任何不相鄰的兩個(gè)點(diǎn)的共同鄰點(diǎn)的個(gè)數(shù)不超過2。因此容易得到下面的引理：

引理1.7交叉折疊超立方體EFH(s,t)中不含3圈，并且任何不相鄰的兩個(gè)點(diǎn)的共同鄰點(diǎn)的個(gè)數(shù)不超過2個(gè)。

2 主要結(jié)論

定理2.1κ(1)(EFH(s,t))=2s+2,1≤s≤t。

證明首先我們證明κ(1)(EFH(s,t))≤2s+2,1≤s≤t。

設(shè)(u,v)∈E2?E(EFH(s,t))并且X={u,v},S=NEFH(s,t)-X(X)。根據(jù)性質(zhì)1.6，我們知道由點(diǎn)u,v誘導(dǎo)的圖是Qs的一條邊。因?yàn)镋FH(s,t)不含3圈，所以|S|=2s+2。由于|X∪S|=2s+4<2s+t+1，即知S是EFH(s,t)的一個(gè)點(diǎn)割?，F(xiàn)在我們證明S是EFH(s,t)的一個(gè)超點(diǎn)割。設(shè)Y=EFH(s,t)-S且w是Y中的一個(gè)點(diǎn)。由引理1.7可知，w在S中至多有兩個(gè)鄰點(diǎn)。因此w在Y中至少有s+2-2(≥1)個(gè)鄰點(diǎn)。因此S是EFH(s,t)的一個(gè)超點(diǎn)割，即知κ(1)(EFH(s,t))≤2s+2,1≤s≤t。

接下來我們將證明κ(1)(EFH(s,t))≥2s+2,1≤s≤t。 設(shè)K?V(EFH(s,t))并且|K|≤2s+1使得EFH(s,t)-K中無孤立點(diǎn)。下證EFH(s,t)-K是連通的。通過性質(zhì)1.5，可知EFH(s,t)=L⊕R。

設(shè)KL=K∩L且KR=K∩R。不失一般性可假設(shè)|KL|≥|KR|， 則 |KR|≤s。考慮下面兩種情形：

情形 1R-KR是連通的

我們將證明L-KL中的任意一個(gè)點(diǎn)u與R-KR是連通的。考慮下面兩種情形：

情形 1.1u=0as-2…a0bt-1…b00

圖2 定理2.1證明中情形1.1的解釋

設(shè)Pi是起點(diǎn)為u且由序列wi=(i-(s+t))(i∈{t+1,t+2,…,s+t-1}{k})所確定的路(看圖2(a))。即Pi的路徑如下：

設(shè)Pk是起點(diǎn)為u且由序列wk=(0-1-0-(s+t))所決定的路。即Pk的路徑如下：

由情形 1.1.1的討論，又因?yàn)镋FH(s,t)中不含3圈， 所以下面命題成立。

反應(yīng)性水腫 對(duì)于體重偏重及不愛活動(dòng)的中老年人來說，夏季是比較難熬的。受高溫的影響，他們的皮膚血管會(huì)發(fā)生擴(kuò)張，引起動(dòng)脈血流量增加和毛細(xì)血管濾過壓增高。此時(shí)若久坐不運(yùn)動(dòng)，就會(huì)導(dǎo)致體液滲透并積聚于皮下組織而腫脹。對(duì)此情況，一方面不必太過擔(dān)心，炎熱的夏天一過，自會(huì)好轉(zhuǎn)；另一方面，積極減肥和適當(dāng)運(yùn)動(dòng)也會(huì)很大程度上避免水腫。

命題2.1存在2s條連接u(或者u0)到R中的某個(gè)點(diǎn)的點(diǎn)不交路。

情形1.1.2u0=0as-2…a0bt-1…b01

設(shè)Pi是起點(diǎn)為u且由序列wi=(i-(s+t))(i∈{t+1,t+2,…,s+t-1})所確定的路(看圖2(b))。即Pi的路徑如下：

通過上面的分析下面命題成立。

命題2.2存在s+t(≥2s)條連接u(或者u0)到R中某一點(diǎn)的點(diǎn)不交路。

圖3 定理2.1證明中情形1.2的解釋

設(shè)Pi是起點(diǎn)為u且由序列wi=(i-0-(s+t))(i∈{1,2,…,t}{k})所決定的路(見圖3(a))，即Pi的路徑如下:

設(shè)Pk的路徑如下:

u=0as-2…a0bt-1…b01→0as-2…a0bt-1…b00→1as-2…a0bt-1…b00。

設(shè)Pi'是起點(diǎn)為u0且由序列wi'=(i-0-(s+t))(i∈{1,2,…,t}{k})所決定的路，即Pi'的路徑如下:

通過上面的分析下面命題成立。

命題2.3存在2t+1(≥2s+1)條連接u(或者u0) 到R中某一點(diǎn)的點(diǎn)不交路。

情形1.2.2u0=0as-2…a0bt-1…b00

設(shè)Pi是起點(diǎn)為u且由序列wi=(i-0-(s+t))(i∈{1,2,…t})所決定的路(見圖3(b))，即Pi的路徑如下:

通過上面的分析下面命題成立。

命題2.4存在s+t+1(≥2s+1)條連接u(或者u0)到R中某一點(diǎn)的點(diǎn)不交路。

命題2.3和命題2.4表明了在情形1.2中我們可以找到至少2s+1條連接u(或者u0)到R中某一點(diǎn)的點(diǎn)不交路。因?yàn)閨K|≤2s+1，所以移除K至多破壞這些路中的2s條，于是一定存在一條連接L-KL中的任意一點(diǎn)u到R-KR中某一點(diǎn)的點(diǎn)不交路，那么EFH(s,t)-K是連通的，因此κ(1)(EFH(s,t))≥2s+2, 即有κ(1)(EFH(s,t))=2s+2,1≤s≤t。

情形2R-KR是不連通的。

通過情形1和情形2的分析，定理2.1成立。

通過EFH(s,t)的定義，我們有ξ(EFH(s,t))=2s+2,s≤t。 在文獻(xiàn)[19]中，作者證明了除了星圖任何點(diǎn)數(shù)超過4的圖G有λ(1)(G)≤ξ(G)。因此有λ(1)(EFH(s,t))≤2s+2。定理2.2中若K是一個(gè)邊集可用同樣的方法證明，即可得λ(1)(EFH(s,t))≥2s+2。于是有下面定理成立。

定理2.2λ(1)(EFH(s,t))=2s+2,1≤s≤t。

3 小結(jié)

在這篇文章中，我們證明了κ(1)(EFH(s,t))=λ(1)(EFH(s,t))=2s+2,1≤s≤t。

設(shè)h是一個(gè)正整數(shù)，一個(gè)圖G的h-限制性連通度(h-限制性邊連通度)[6，20-21]是G刪除G中的某個(gè)點(diǎn)子集(邊子集)，如果存在這樣的子集，使得G不連通且每個(gè)分支中點(diǎn)的度數(shù)至少是h的最小點(diǎn)集(邊集)的基數(shù)。容易知κ(0)(G)=κ(G)(λ(0)(G)=λ(G))并且1-限制性連通度(1-限制性邊連通度)又稱為超連通度(超邊連通度)。h-限制性連通度參數(shù)是傳統(tǒng)連通度參數(shù)的一個(gè)廣義化， 并且它提高了連通度測量的準(zhǔn)確性。研究表明如果互連網(wǎng)絡(luò)有限制性連通度的特性則它是更可靠的并且比其它網(wǎng)絡(luò)有一個(gè)更低的點(diǎn)的容錯(cuò)率，一個(gè)自然而有趣的問題是確定κ(h)(EFH(s,t))和λ(h)(EFH(s,t))。