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

葉彩月， 馬美杰， 王維凡

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

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

以 u，v為端點(diǎn)的邊記為(u，v);以 u，v為端點(diǎn)的路用 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個(gè)端點(diǎn)相同的路稱(chēng)為圈，記為C．包含圖中所有點(diǎn)的路稱(chēng)為哈密頓路;包含圖中所有點(diǎn)的圈稱(chēng)為哈密頓圈．如果圖中有一條哈密頓圈，則稱(chēng)它是哈密頓的;如果圖中任何2個(gè)不同點(diǎn)之間都有哈密頓路，則稱(chēng)它是哈密頓連通的．若圖的頂點(diǎn)集可以劃分為2個(gè)非空子集Vw和Vb，使得對(duì)圖的任意一條邊(u，v)∈E，有 u∈Vw，v∈Vb，則稱(chēng)該圖為二部圖，記為 G=(Vw∪Vb，E)．在二部圖中，如果位于不同部分的任意2個(gè)頂點(diǎn)u∈Vw，v∈Vb之間都有哈密頓路，則稱(chēng)二部圖是哈密頓Laceable．

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

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

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

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

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

1)當(dāng)0≤fav≤n-2，fe+fav≤n-2 時(shí)，Qn-F 是哈密頓的;

2)當(dāng)0≤fav≤n-3，fe+fav≤n-2 時(shí)，Qn-F 是哈密頓 Laceable．

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

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

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

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

當(dāng)n=4時(shí)，fav=0，fe≤3或 fav=1，fe≤1，由引理1和引理2知，定理1成立．

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

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

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

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

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

則

不妨設(shè)

則

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

下證對(duì)Qn-F中的任意位于不同部分的2個(gè)點(diǎn)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)為非故障邊，且點(diǎn) xR，yR為非故障點(diǎn)(其中 xR與 yR分別表示 x與 y在 R 中的鄰點(diǎn))．記 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中存在點(diǎn)z∈Vb，使得(z，zR)為非故障邊，且zR為非故障點(diǎn)(其中zR表示點(diǎn)z在R中的鄰點(diǎn))．根據(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中存在一對(duì)相鄰故障點(diǎn)對(duì){w1，b1}，使得L-(FL-{w1，b1})中位于不同部分的任意兩點(diǎn)w'∈Vw，b'∈Vb在L-(FL-{w1，b1})中存在一條哈密頓路P連接w'和b'，滿足w1與b1在路P上的鄰點(diǎn)不與L之外的故障邊關(guān)聯(lián)．

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

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

因此，斷言1成立．

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

情形2．1 w，b∈V(L-FL)．由斷言1 知，存在一對(duì)相鄰故障點(diǎn)對(duì){w1，b1}，使得L-(FL-{w1，b1})中存在一條哈密頓路P(w，b)，滿足w1與b1在路P上的鄰點(diǎn)不與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中的所有點(diǎn)．因此，在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 知，存在一對(duì)相鄰故障點(diǎn)對(duì){w1，b1}，使得L-(FL-{w1，b1})中存在一條哈密頓路P(w，b1)，滿足w1與b1在路P上的鄰點(diǎn)不與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中的所有點(diǎn)．因此，在Qn-F中存在一條哈密頓路(如圖1(b)所示)

如果zR=b，則由引理5知，R-FR-{b}中有哈密頓路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)．當(dāng) n=5，fRe=1時(shí)，分以下2種情形討論:

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

當(dāng)(x，y)?E(C)時(shí)，與①類(lèi)似，在Qn-F中存在一條哈密頓路P(w，b)．

綜上所述，定理1得證．

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

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

圖2 Q3，Q4中無(wú)哈密頓路的情形

［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．