故障加強(qiáng)超立方體中的邊泛圈

張艷娟,劉紅美

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

1 引言

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

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

2 定義和概念

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

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

n維超立方體Qn是一個(gè)簡(jiǎn)單圖,其每個(gè)點(diǎn)x都可以用一個(gè)長(zhǎng)為n的二元位串表示.即點(diǎn)集V(Qn)={x1x2···xn:xi={0,1},i=1,2,···,n}. 兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們對(duì)應(yīng)的字符串中有且只有一位不同,即點(diǎn)x=x1x2···xn和y之間有邊相連當(dāng)且僅當(dāng)y滿足：中兩個(gè)頂點(diǎn)x=x1x2···xn和y=y1y2···yn之間的Hamming距離定義為即表示兩頂點(diǎn)的二元字符串中對(duì)應(yīng)的不同分量的個(gè)數(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作為超立方體的一種簡(jiǎn)單變型,它的頂點(diǎn)集和Qn的頂點(diǎn)集一樣,只不過是通過在Qn中添加一些補(bǔ)邊所得到的.它是這樣定義的：

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

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

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

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

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

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

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

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

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

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

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

3 點(diǎn)容錯(cuò)下加強(qiáng)超立方體中邊泛圈的嵌入

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

3.1 邊偶泛圈嵌入加強(qiáng)超立方體

3.2 邊奇泛圈嵌入加強(qiáng)超立方體

4 (n?2)-點(diǎn)容錯(cuò)下加強(qiáng)超立方體中邊偶泛圈的嵌入

5 小結(jié)

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

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

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