故障加強超立方體中的邊泛圈

張艷娟,劉紅美

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

1 引言

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

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

2 定義和概念

文中沒有說明的符號和定義參看文獻[3].由于系統可以用圖表示,我們經常用圖的概念來表示網絡的概念.G=(V,E)表示一個簡單無向圖,其中V為點集,E為邊集.設x和y是圖G中兩頂點,連接x和y長度為k的xy路(path),記為xy路或是P[x,y],是指點和邊交替出現的序列P=v0(=x)e1v1e2v2···vi?1eivi···ekvk(=y),且除點x和y外,其余的頂點互不相同,邊ei的端點是vi?1和vi,x和y稱為P的端點(end-vertices),其余的頂點稱為內部點(internal vertices).P中邊的數目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(G)≤l≤v(G),g(G)是圖G的圍長,v(G)是圖G的階,稱圖G是泛圈的.如果圖G是泛圈的,則一定是哈密頓的.網絡是否具有泛圈性可以度量該網絡是否可以嵌入任意長度的圈.泛圈性的概念被推廣到點泛圈性和邊泛圈性.如果圖G的每個頂點位于長從g(G)到v(G)的圈上,則稱G是點泛圈的(vertex-pancyclic).如果圖的每條邊位于長從g(G)到v(G)的圈上,則稱G是邊泛圈的(edge-pancyclic).顯然,邊泛圈的圖一定是點泛圈的.因為二部圖不含奇圈,故對二部圖提出了偶泛圈的概念.如果圖G含有長為l的偶圈,其中g(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}. 兩個頂點相鄰當且僅當它們對應的字符串中有且只有一位不同,即點x=x1x2···xn和y之間有邊相連當且僅當y滿足：中兩個頂點x=x1x2···xn和y=y1y2···yn之間的Hamming距離定義為即表示兩頂點的二元字符串中對應的不同分量的個數（或表示為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有一條邊相連當且僅當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)個坐標將其分成兩個子圖.我們用分別來表示這兩部分.一個點x=x1x2...xn屬于當且僅當該點的第i位xi=0.同樣地,一個點x=x1x2...xn屬于當且僅當該點的第i位xi=1.當i

引理3(見文獻[14]) 若fv≤n?2,則Qn中任意兩相鄰節點之間均存在長度從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中故障邊的數目,fv表示Qn中故障頂點的數目.

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

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

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

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

首先討論當|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 小結

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

(1)當|Fv|=1時,若n和k有相同奇偶性,則Qn,k中每一條邊均在長度從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的奇圈上.

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