超立方體網(wǎng)絡(luò)的容錯哈密頓Laceability＊

葉彩月， 馬美杰， 王維凡

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

人們通常用連通的簡單圖G=(V，E)表示互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)，其中V和E分別表示圖G的點集和邊集．本文未定義的記號和術(shù)語見文獻［1］．

以 u，v為端點的邊記為(u，v);以 u，v為端點的路用 P(u，v)或 P(u，v)=〈u，P(u，s)，s，t，P(t，v)，v〉表示，其中P(u，s)和P(t，v)分別表示P(u，v)中u到s的子路和t到v的子路;用E(P)表示路P的邊集;2個端點相同的路稱為圈，記為C．包含圖中所有點的路稱為哈密頓路;包含圖中所有點的圈稱為哈密頓圈．如果圖中有一條哈密頓圈，則稱它是哈密頓的;如果圖中任何2個不同點之間都有哈密頓路，則稱它是哈密頓連通的．若圖的頂點集可以劃分為2個非空子集Vw和Vb，使得對圖的任意一條邊(u，v)∈E，有 u∈Vw，v∈Vb，則稱該圖為二部圖，記為 G=(Vw∪Vb，E)．在二部圖中，如果位于不同部分的任意2個頂點u∈Vw，v∈Vb之間都有哈密頓路，則稱二部圖是哈密頓Laceable．

大型互連網(wǎng)絡(luò)的結(jié)點和連線在使用過程中難免會發(fā)生故障，因此考慮發(fā)生故障的網(wǎng)絡(luò)具有現(xiàn)實意義．如果對圖G的任意故障點(或邊)集F?V(G)(或E(G))且|F|≤k，圖G-F仍是哈密頓的，則稱圖G是k點(或邊)容錯哈密頓的．對二部圖G的任意故障集F?V(G)∪E(G)且|F|≤k，圖G-F仍是哈密頓Laceable，則稱圖G是k容錯哈密頓Laceable．

n維超立方體網(wǎng)絡(luò)Qn(或簡稱為n立方體)由2n個頂點構(gòu)成，每個頂點v用一個n位二進制串v0v1…vn-1表示．2個頂點相連當且僅當2個頂點對應(yīng)的二進制串恰有一位分量不同．特別地，Qn是點可遷和邊可遷的二部圖(Vw∪Vb，E)［1］．

由Qn的定義知，Qn可分解為2個Qn-1添加一些邊集構(gòu)成:Qn=Lk⊙Rk．其中:Lk表示Qn中第k個分量為0的點導(dǎo)出的子圖;Rk表示Qn中第k個分量為1的點導(dǎo)出的子圖．Qn中連接Lk和Rk的2n-1條邊稱為Qn的k維邊，記為Ek．稱Qn=Lk⊙Rk為Qn的一個k維劃分．

引理1［2］當n≥3時，超立方體網(wǎng)絡(luò)Qn的fe條故障邊集設(shè)為Fe．若fe≤2n-5，且Qn-Fe中每個頂點至少與2條非故障邊相關(guān)聯(lián)，則Qn-Fe是哈密頓Laceable．

引理2［3］當n≥3時，超立方體網(wǎng)絡(luò)Qn的故障集為F=Fav∪Fe．其中:Fe表示fe條故障邊集;Fav表示fav對不相交的相鄰故障點對集．則

1)當0≤fav≤n-2，fe+fav≤n-2 時，Qn-F 是哈密頓的;

2)當0≤fav≤n-3，fe+fav≤n-2 時，Qn-F 是哈密頓 Laceable．

引理3［3］當n≥3時，超立方體網(wǎng)絡(luò) Qn=(Vb∪Vw，E)的 fe條故障邊集設(shè)為 Fe．若 fe≤n-3，則在Qn-Fe中任意點 w'，w"∈Vw，b'，b"∈Vb間有 2 條內(nèi)不交的路 P(w'，b')和 P(w"，b")，分別連接 w'，b'和 w"，b"，且 V(P(w'，b'))∪V(P(w"，b"))=V(Qn)．

引理4［3］當n≥4時，超立方體網(wǎng)絡(luò)Qn=(Vb∪Vw，E)的 fe條故障邊集設(shè)為Fe．若fe≤n-4，則任意點 w，w'∈Vw，b，b'∈Vb在 Qn-Fe-{w'，b'}中存在一條哈密頓路 P(w，b)．

引理5［4］當n≥3時，超立方體網(wǎng)絡(luò)Qn=(Vb∪Vw，E)的 fe條故障邊集設(shè)為Fe．若fe≤n-3，則任意點 w'，w"∈Vw，b'∈Vb在 Qn-Fe-{b'}中存在一條哈密頓路 P(w'，w")．

定理1 當n≥3時，超立方體網(wǎng)絡(luò)Qn的故障集為F=Fav∪Fe．其中:Fe表示fe條故障邊集;Fav表示fav對不相交的相鄰故障點對集．若0≤fav≤n-3，fe+2fav≤2n-5，且Qn-F中每個頂點至少與2條非故障邊相關(guān)聯(lián)，則Qn-F是哈密頓Laceable．

證明 對超立方體的維數(shù)n(n≥3)用數(shù)學(xué)歸納法證明．當n=3時，fav=0，fe≤1，由引理1知，定理1成立．

當n=4時，fav=0，fe≤3或 fav=1，fe≤1，由引理1和引理2知，定理1成立．

設(shè)定理1在Qn-1中成立．下證定理1在Qn(n≥5)中也成立．

由引理1知，當 fav=0 時，定理1成立．下設(shè)1≤fav≤n-3．因為 fe+2fav≤2n-5，所以 fe≤2n-7．在Qn-F中至多有1個點與n-2條故障邊相關(guān)聯(lián)．否則，如果存在2個點與n-2條故障邊相關(guān)聯(lián)，那么fe≥2n-5，這與 fe≤2n-7 矛盾．用 Eav={(wi，bi)|{wi，bi}?Fav}表示故障點對之間的邊集．因此

1)若存在一個點v與n-2條故障邊集Ev相關(guān)聯(lián)，則由于故障點對集fav≤n-3，因此存在Qn的一個 k 維劃分，使得 Ev∩Ek=1，Ek∩Eav= φ;

2)若每個點都至多與n-3條故障邊相連，則存在Qn的一個k維劃分，使得Ek∩Eav=φ．

所以，存在Qn的一個劃分Qn=L⊙R，使得L和R中任意一點都至少與2條非故障邊相關(guān)聯(lián)，且故障點對{wi，bi}∈V(L)或者{wi，bi}∈V(R)．將連接 L 和 R 的邊集記為 Ec．令

則

不妨設(shè)

則

因此R滿足歸納假設(shè)，即R-FR是哈密頓Laceable．

下證對Qn-F中的任意位于不同部分的2個點w∈Vw，b∈Vb存在一條哈密頓路連接w和b．分以下2種情形討論:

情形 1．1 w，b∈V(L-FL)或 w，b∈V(R-FR)，不妨設(shè) w，b∈V(L-FL)．

由歸納假設(shè)知，在L-FL中存在一條哈密頓路P(w，b)．由于

因此，在路 P(w，b)上存在一條邊(x，y)，使得邊(x，xR)，(y，yR)為非故障邊，且點 xR，yR為非故障點(其中 xR與 yR分別表示 x與 y在 R 中的鄰點)．記 P(w，b)=〈w，P(w，x)，x，y，P(y，b)，b〉．根據(jù)歸納假設(shè)，在R-FR中有一條哈密頓路P(xR，yR)，因此在Qn-F中有一條哈密頓路

情形 1．2w∈V(L-FL)，b∈V(R-FR)或者 w∈V(R-FR)，b∈V(L-FL)．不妨設(shè) w∈V(L-FL)，b∈V(R-FR)．

在L-FL中存在點z∈Vb，使得(z，zR)為非故障邊，且zR為非故障點(其中zR表示點z在R中的鄰點)．根據(jù)歸納假設(shè)，在L-FL和R-FR中分別有一條哈密頓路P(w，z)和P(zR，b)，因此在Qn-F中有一條哈密頓路 P(w，b)=〈w，P(w，z)，z，zR，P(zR，b)，b〉．

斷言1 在L-FL中存在一對相鄰故障點對{w1，b1}，使得L-(FL-{w1，b1})中位于不同部分的任意兩點w'∈Vw，b'∈Vb在L-(FL-{w1，b1})中存在一條哈密頓路P連接w'和b'，滿足w1與b1在路P上的鄰點不與L之外的故障邊關(guān)聯(lián)．

證明 如果Fc=φ，則由歸納假設(shè)知，L-(FL-{w1，b1})中有一條哈密頓路P連接w'和b'，顯然w1與b1在路P上的鄰點不與L之外的故障邊關(guān)聯(lián)．

如果 Fc={(u，v)}者存在故障點wi與u之間的鄰邊是故障邊，并設(shè)此故障點為w1，則由歸納假設(shè)知，L-(FL-{w1，b1})中有一條哈密頓路P連接w'和b'，顯然w1在P上的鄰點不能為u．如果任意故障點wi都與u相鄰且鄰邊都是非故障邊，則由故障點對fav≥1知，在L中存在故障點(設(shè)為w1)與u相鄰，且邊(u，w1)是非故障邊．由歸納假設(shè)知，L-(FL-{w1，b1})-(u，w1)中有一條哈密頓路P連接w'和b'，使得u與w1在P上不相鄰．

因此，斷言1成立．

根據(jù)斷言1，分下列3種子情形來構(gòu)造Qn-F中連接w與b的哈密頓路:

情形2．1 w，b∈V(L-FL)．由斷言1 知，存在一對相鄰故障點對{w1，b1}，使得L-(FL-{w1，b1})中存在一條哈密頓路P(w，b)，滿足w1與b1在路P上的鄰點不與L之外的故障邊關(guān)聯(lián)．

如果(w1，b1)?E(P(w，b))，并設(shè) P(w，b)=〈w，P(w，s)，s，w1，t，P(t，x)，x，b1，y，P(y，b)，b〉，且(s，sR)，(t，tR)，(x，xR)，(y，yR)都是非故障邊，則由引理3 知，在 R-FR中存在 2 條內(nèi)不交路 P(sR，xR)和P(tR，yR)包含R-FR中的所有點．因此，在Qn-F中存在一條哈密頓路(如圖1(a)所示)

如果(w1，b1)∈E(P(w，b))，并設(shè) P(w，b)=〈w，P(w，x)，x，w1，b1，y，P(y，b)，b〉，則由引理 1 知，R-FR中有哈密頓路P(xR，yR)，因此在Qn-F中存在一條哈密頓路

圖1 Qn-F中的哈密頓路

情形2．2 w∈V(L-FL)，b∈V(R-FR)．由斷言 1 知，存在一對相鄰故障點對{w1，b1}，使得L-(FL-{w1，b1})中存在一條哈密頓路P(w，b1)，滿足w1與b1在路P上的鄰點不與L之外的故障邊關(guān)聯(lián)．

如果(w1，b1)?E(P(w，b1))，則可設(shè) P(w，b1)=〈w，P(w，x)，x，w1，y，P(y，z)，z，b1〉．如果 zR≠b，則由引理3知，在R-FR中存在2條內(nèi)不交路P(xR，zR)和P(yR，b)包含R-FR中的所有點．因此，在Qn-F中存在一條哈密頓路(如圖1(b)所示)

如果zR=b，則由引理5知，R-FR-中有哈密頓路P(xR，yR)．因此，Qn-F中存在一條哈密頓路

如果(w1，b1)∈E(P(w，b1))，并設(shè) P(w，b1)=〈w，P(w，x)，x，w1，b1〉，則由引理 1 知，R-FR中有哈密頓路P(xR，b)．因此，Qn-F中存在一條哈密頓路

情形 2．3 w，b∈V(R-FR)．當 n=5，fRe=1時，分以下2種情形討論:

如果 xR≠b，yR=w 或者 xR=b，yR≠w，不妨設(shè) xR≠b，yR=w，則由引理5 知，R-FR-中存在哈密頓路P(w，yR)．因此，Qn-F中有一條哈密頓路

當(x，y)?E(C)時，與①類似，在Qn-F中存在一條哈密頓路P(w，b)．

綜上所述，定理1得證．

注1 如果故障點對fav=n-2，則定理1不成立．如在Q3中，當點000，010為故障點對時，Q3中點101到點111無哈密頓路(如圖2(a)所示)．故定理1中的界0≤fav≤n-3是緊的．

注2 如果故障數(shù)fe+2fav=2n-4，則定理1不成立．如在Q4中，當點0000，0010為故障點對，(0110，1110)，(0011，1011)為2條故障邊時，Q4中任意一點都至少關(guān)聯(lián)于2條非故障邊，此時fe+2fav=2+2=8-4=4，而點0101到點0111無哈密頓路(如圖2(b)所示)．故定理1中的界fe+2fav≤2n-5是緊的．

圖2 Q3，Q4中無哈密頓路的情形

［1］徐俊明．組合網(wǎng)絡(luò)理論［M］．北京:科學(xué)出版社，2007．

［2］Tsai C H．Linear array and ring embeddings in conditional faulty hypercubes［J］．Theoretical Computer Science，2004，314(3):431-443．

［3］Hung Chunnan，Chang Yihua，Sun Chaoming．Longest paths and cycles in faulty hypercubes［C］//Proceedings of the 24th IASTED International Conference on Parallel and Distributed Computing and Networks．Innsbruck:ACTA Press Anaheim，2006:101-110．

［4］Tsai C H，Jimmy J M T，Hsu L H．Fault-tolerant hamiltonian laceability of hypercubes［J］．Information Processing Letters，2002，83(6):301-306．