張艷娟,劉紅美

(三峽大學(xué)理學(xué)院,湖北 宜昌 443002)

1 引言

基于VLSI技術(shù)的迅猛發(fā)展,一個多處理機系統(tǒng)含有大量的節(jié)點.在系統(tǒng)實現(xiàn)過程中,無論節(jié)點還是鏈接發(fā)生故障的可能性都是不可避免的,因此對系統(tǒng)作容錯性能分析是非常重要的課題.當(dāng)故障發(fā)生時,一個系統(tǒng)能保持一定的功能,則稱該系統(tǒng)是容錯的.判斷一個系統(tǒng)是否保持一定功能的標(biāo)準(zhǔn)之一就是看系統(tǒng)是否含有某種拓?fù)浣Y(jié)構(gòu),這種問題經(jīng)常表現(xiàn)為把一種結(jié)構(gòu)嵌入到另一種結(jié)構(gòu)中.本文主要關(guān)注在節(jié)點發(fā)生故障時,系統(tǒng)中每條鏈接是否在各種長度的圈型結(jié)構(gòu)中.通常用G=(V,E)來表示一個圖,圖的頂點集V表示網(wǎng)絡(luò)節(jié)點集合(或稱點集),圖的邊集E表示網(wǎng)絡(luò)鏈接集合(或稱邊集).網(wǎng)絡(luò)G中最小圈長,稱為G的圍長,用g(G)表示.若圖G含有長為l的圈,其中g(shù)(G)≤l≤v(G),v(G)=|V|是G的節(jié)點數(shù)（或稱階）,則稱G是泛圈的(pancyclic).網(wǎng)絡(luò)是否具有泛圈性可以度量該網(wǎng)絡(luò)是否可以嵌入任意長度的圈.若G中每條邊均位于長從g(G)到v(G)的圈上,則稱G是邊泛圈的(edge-pancyclic)．若含有從g(G)到v(G)的所有偶數(shù)長度的圈(簡稱偶圈),稱G是偶泛圈的(bipancyclic)；若對G中的每條邊,均存在長度從g(G)到v(G)的所有偶圈經(jīng)過該邊,則稱G是邊偶泛圈的(edge-bipancyclic)．如果G的點集可以劃分為兩個非空不交子集X、Y,使得G中每條邊的端點分別屬于X、Y,則稱G為二部圖.二部圖不含長度為奇數(shù)的圈（簡稱奇圈）.因此二部圖僅研究其偶泛圈性和邊偶泛圈性.以超立方體為拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)簡稱超立方體網(wǎng)絡(luò),它是典型的二部圖,由于其結(jié)構(gòu)正則,對稱,具有點邊傳遞性、相對小的傳輸延遲、路可嵌入性、圈可嵌入性、樹能以膨脹系數(shù)1嵌入等優(yōu)良性質(zhì)而受到廣泛關(guān)注(見文獻[1–3]),在高性能計算機中,尤其在大型工業(yè)計算和研究中,超立方體結(jié)構(gòu)有著非常重要的作用.n-維超立方體,記為Qn.隨著可靠性容錯性要求的越來越高,許多改進的超立方體拓?fù)浣Y(jié)構(gòu)相繼提出,比如折疊超立方體FQn,加強超立方體Qn,k,可擴超立方體AQn,交叉超立方體CQn,廣義超立方體等等[3].

超立方體及其變形結(jié)構(gòu)的泛圈性以及容錯泛圈性的研究近來得到了許多好的結(jié)果.文獻[4]證明了Qn,k為二部圖當(dāng)且僅當(dāng)n和k有相同奇偶性．因此,當(dāng)n和k有相同奇偶性時,對Qn,k需要考慮偶泛圈的嵌入;當(dāng)n和k有不同奇偶性時,要同時考慮奇圈和偶圈的嵌入．文獻[5]證明了當(dāng)|Fv|=1時,若n和k有相同奇偶性,則Qn,k中存在長度從4到2n?2的偶圈；若n和k奇偶性不同,則Qn,k中不僅存在長度從4到2n?2的偶圈,而且還存在長度從n?k+2到2n?1的所有奇圈.在此基礎(chǔ)上,文獻[6]進一步證明了當(dāng)|Fv|=2,若n和k有相同奇偶性,則Qn,k中存在長度從4到2n?4的偶圈；若n和k有不同奇偶性,則在Qn,k中不僅存在長度從4到2n?4的偶圈,而且還存在長度從n?k+2到2n?3的奇圈．同時文獻[6]還證明了當(dāng)|Fv|≤n?2時,若n和k奇偶性相同,則Qn,k存在長度2n?2|Fv|的偶圈;若n和k奇偶性不同,則Qn,k存在長度2n?2|Fv|的偶圈,同時存在長度從2n?2|Fv|+1的奇圈.折疊超立方體是加強超立方體中k=1時的一種特殊情形,關(guān)于折疊立方體的容錯性能也有很多好的結(jié)果.文獻[7]證明了在折疊超立方體FQn(n≥4)中,當(dāng)|Fv|=2n?3,FQn?Fv中存在一個長度至少為2n?2|Fv|的圈．文獻[8]進一步推廣上述結(jié)論,證明了在折疊超立方體FQn(n≥3)中,若|Fe|+|Fv|≤2n?3,|Fe|≥1,且FQn中每個點至少關(guān)聯(lián)兩條無故障邊,則在FQn?Fv?Fe中存在一個長度至少為2n?2|Fv|的圈．文獻[9]證明了當(dāng)|Fe|+|Fv|≤2n?4和|Fe|≤n?1時,Qn,k(n≥4)中能找到一條長為2n?2|Fv|的容錯圈.文獻[10]證明了當(dāng)|Fe|≤2n?3且Qn,k中每個點至少關(guān)聯(lián)兩條無故障邊時,若n和k有相同奇偶性,則Qn,k是偶泛圈的；若n和k有不同奇偶性,則在Qn,k中不僅可以構(gòu)造長度從4到2n的偶圈,而且還存在長度從n?k+2到2n?1的奇圈．[11]證明當(dāng)n和k有相同的奇偶性時,Qn,k(n≥3,1≤k≤n?1)是n?2-邊容錯超哈密頓脆弱的,也就是說,若|Fe|≤n?2,FQn?Fe中任意兩個奇偶性不同的點之間存在一條長為2n?1的路．文獻[4]研究了Qn,k的邊泛圈問題,證明了在無故障加強超立方體Qn,k中,當(dāng)n和k有相同奇偶性時,Qn,k中每一條邊均在長度從4到2n?2的偶圈（即Qn,k是邊偶泛圈的）；當(dāng)n和k有不同奇偶性時,Qn,k中每一條邊不僅均在長度從4到2n?2的偶圈上,而且還均在長度從n?k+2到2n?1的奇圈上．然而關(guān)于故障加強超立方體中容錯邊泛圈的嵌入問題目前還沒有相關(guān)研究結(jié)果,本文對Qn,k的結(jié)構(gòu)性質(zhì)作了進一步探討,并證明當(dāng)|Fv|=1時,若n和k有相同奇偶性,則Qn,k中每一條邊均在長度從4到2n?2的偶圈上；當(dāng)n和k有不同奇偶性時,Qn,k中每一條邊不僅均在長度從4到2n?2的偶圈上,而且還均在長度從n?k+4到2n?3的奇圈上.特別的,對于Qn,k中每一條j∈{k,k+1,···,n,c}?維邊,它們還均在長度為n?k+2的奇圈上．同時還證明了當(dāng)|Fv|≤n?2時,Qn,k(1≤k≤n?2)中每一條邊均在長度從4到2n?2|Fv|的偶圈上．

2 定義和概念

文中沒有說明的符號和定義參看文獻[3].由于系統(tǒng)可以用圖表示,我們經(jīng)常用圖的概念來表示網(wǎng)絡(luò)的概念.G=(V,E)表示一個簡單無向圖,其中V為點集,E為邊集.設(shè)x和y是圖G中兩頂點,連接x和y長度為k的xy路(path),記為xy路或是P[x,y],是指點和邊交替出現(xiàn)的序列P=v0(=x)e1v1e2v2···vi?1eivi···ekvk(=y),且除點x和y外,其余的頂點互不相同,邊ei的端點是vi?1和vi,x和y稱為P的端點(end-vertices),其余的頂點稱為內(nèi)部點(internal vertices).P中邊的數(shù)目k稱為P的長度.兩個端點相同的路稱為圈(cycle).在簡單圖中,路P可以表示為P[v0,vk]=(v0,v1,v2,···,vk)．若v0=vk,則稱P為圈(cycle)．包含圖中所有頂點的路稱為哈密頓路(hamiltonian path).包含圖中所有頂點的圈稱為哈密頓圈(hamiltonian cycle).圖G中最短圈的長度稱為G的圍長(girth),記為g(G).圖G中連接點u和v之間的最短路的長度稱為兩點間的距離(distance),記為dG(u,v).對于已知的圖G,簡記為d(u,v).圖中任意兩頂點u和v之間距離的最大值,稱為圖的直徑(diameter),記為D(G).

如果圖G含有長為l的圈,其中g(shù)(G)≤l≤v(G),g(G)是圖G的圍長,v(G)是圖G的階,稱圖G是泛圈的.如果圖G是泛圈的,則一定是哈密頓的.網(wǎng)絡(luò)是否具有泛圈性可以度量該網(wǎng)絡(luò)是否可以嵌入任意長度的圈.泛圈性的概念被推廣到點泛圈性和邊泛圈性.如果圖G的每個頂點位于長從g(G)到v(G)的圈上,則稱G是點泛圈的(vertex-pancyclic).如果圖的每條邊位于長從g(G)到v(G)的圈上,則稱G是邊泛圈的(edge-pancyclic).顯然,邊泛圈的圖一定是點泛圈的.因為二部圖不含奇圈,故對二部圖提出了偶泛圈的概念.如果圖G含有長為l的偶圈,其中g(shù)(G)≤l≤v(G),稱圖G是偶泛圈的(even-pancyclic).如果圖G中的任意兩個頂點x與y之間長為l的路,其中dG(x,y)≤l≤v(G)?1且2|l?dG(x,y),則稱G是偶泛連通的(even-panconnected).

n維超立方體Qn是一個簡單圖,其每個點x都可以用一個長為n的二元位串表示.即點集V(Qn)={x1x2···xn:xi={0,1},i=1,2,···,n}. 兩個頂點相鄰當(dāng)且僅當(dāng)它們對應(yīng)的字符串中有且只有一位不同,即點x=x1x2···xn和y之間有邊相連當(dāng)且僅當(dāng)y滿足：中兩個頂點x=x1x2···xn和y=y1y2···yn之間的Hamming距離定義為即表示兩頂點的二元字符串中對應(yīng)的不同分量的個數(shù)（或表示為dH(x,y)）．由定義可知,在Qn中dQn(x,y)=dH(x,y)．稱連接u,ui之間的邊(u,ui)為Qn中的i-維邊,記Ei={(u,ui)|h(u,ui)=1,i∈{1,2,···,n}},因此

Qn,k作為超立方體的一種簡單變型,它的頂點集和Qn的頂點集一樣,只不過是通過在Qn中添加一些補邊所得到的.它是這樣定義的：

定義1加強超立方體Qn,k=(V,E)(1≤k≤n?1)是一個簡單無向圖.它和超立方體有一樣的頂點集即V={x1x2···xn:xi=0 or 1,1≤i≤n}.兩頂點x=x1x2···xn和y有一條邊相連當(dāng)且僅當(dāng)y滿足下列兩個條件之一

由加強超立方體Qn,k的定義可以看出加強超立方體Qn,k包含超立方體Qn作為它的子圖.加強超立方體Qn,k是在超立方體Qn中添加2n?1條補邊（the complementary edge）后得到的,即E(Qn,k)=Ec∪E(Qn),其中為補邊集．邊(u,ui)為Qn,k中的i-維超立方體的邊,于是E(Qn,k)=Ec∪E1∪E2∪···∪En．

下面給出主要證明很重要的一些引理.

引理1(見文獻[12]) 在超立方體Qn(n≥3)中,若fv≤n?2,則Qn中每一條無故障邊均在長度從4到2n?2fv的圈上.

引理2(見文獻[13]) 加強立方體Qn,k(1≤k≤n?1)能夠沿著頂點的第i(1≤i≤n)個坐標(biāo)將其分成兩個子圖.我們用分別來表示這兩部分.一個點x=x1x2...xn屬于當(dāng)且僅當(dāng)該點的第i位xi=0.同樣地,一個點x=x1x2...xn屬于當(dāng)且僅當(dāng)該點的第i位xi=1.當(dāng)i

引理3(見文獻[14]) 若fv≤n?2,則Qn中任意兩相鄰節(jié)點之間均存在長度從3到2n?2fv?1的奇長的路．

引理4(見文獻[15])Qn(n≥3)中,任意兩點u和v之間均存在長度為l的路,且dH(u,v)≤l≤2n?1,且l與dH(u,v)同奇偶.

引理5(見文獻[16]) 如果|Fe|+|Fv|≤n?2,則Qn中任意兩點u和v之間均存在長度為l的路,dH(u,v)+2≤l≤2n?2fv?1,且l與dH(u,v)同奇偶,其中fe表示Qn中故障邊的數(shù)目,fv表示Qn中故障頂點的數(shù)目.

引理6(見文獻[1]) 設(shè)u和v是Qn中任意兩點,且dQn(u,v)=d,則在Qn中存在n條內(nèi)點不交的路,其中d條長度為d,n?d條長度為d+2.

引理7(見文獻[17]) 超立方體Qn(n≥4)中,當(dāng)fv=n?1且Qn中每個點至少關(guān)聯(lián)兩個無故障點時,Qn中每一條邊均在長度從6到2n?2fv的偶圈上．

引理8(見文獻[15]) 超立方體Qn(n≥3)中每一條邊均在長度從4到2n的偶圈上．

3 點容錯下加強超立方體中邊泛圈的嵌入

首先討論當(dāng)|Fv|=1時,若n和k有相同奇偶性,則Qn,k(n≥4)中每一條邊均在長度從4到2n?2的偶圈上；若n和k有不同奇偶性,則Qn,k中每一條邊不僅均在長度從4到2n?2的偶圈上,而且還均在長度從n?k+4到2n?3的奇圈上,特別的對于Qn,k中每一條j∈{k,k+1,···,n,c}-維邊它們還均在長度為n?k+2的奇圈上,而對于Qn,k中每一條j∈{1,2,···,k?1}-維邊則不能保證它們均在長度為n?k+2的奇圈上,例如Q4,3中的1-維邊(0001,1001)就不在長度為n?k+2=3的圈上,2-維邊(0101,0001)也不在長度為n?k+2=3的圈上,但長在為5的奇圈上,即0001→1001→1000→0000→0010→0001.

3.1 邊偶泛圈嵌入加強超立方體

3.2 邊奇泛圈嵌入加強超立方體

4 (n?2)-點容錯下加強超立方體中邊偶泛圈的嵌入

5 小結(jié)

網(wǎng)絡(luò)是否具有泛圈性可以度量該網(wǎng)絡(luò)是否可以嵌入任意長度的圈.加強超立方體是超立方體的變形結(jié)構(gòu),其連通性、安全性、可靠性以及傳輸延遲等性質(zhì)都優(yōu)于超立方體,對其性能和容錯性的研究是非常重要的.本文主要探討含有故障點的加強超立方體的邊泛圈性.得到了如下結(jié)論

(1)當(dāng)|Fv|=1時,若n和k有相同奇偶性,則Qn,k中每一條邊均在長度從4到2n?2的圈上；當(dāng)n和k有不同奇偶性時,Qn,k中每一條邊不僅均在長度從4到2n?2的偶圈上,而且還均在長度從n?k+4到2n?3的奇圈上,特別的對于Qn,k中每一條j(∈{k,k+1,···,n,c})-維邊它們還均在長度為n?k+2的奇圈上.

(2)當(dāng)|Fv|≤n?2時,Qn,k中每一條邊均在長度從4到 2n?2|Fv|的偶圈上．當(dāng)n和k有不同奇偶性時,對含有更多故障節(jié)點和故障邊的加強超立方體Qn,k的邊奇泛圈性質(zhì)的研究是下一步的工作.