邊容錯(cuò)3元n立方體的兩條等長(zhǎng)不交覆蓋路

佘衛(wèi)強(qiáng)

（漳州職業(yè)技術(shù)學(xué)院通識(shí)教育學(xué)院,福建漳州 363000）

在并行算法處理和并行計(jì)算系統(tǒng)中，超立方體有許多優(yōu)良性質(zhì)，使得它成為當(dāng)今最有效，最常用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).1977 年第一臺(tái)超立方體并行處理機(jī)問(wèn)世，隨后互連網(wǎng)飛躍發(fā)展，網(wǎng)絡(luò)系統(tǒng)越來(lái)越復(fù)雜，同時(shí)計(jì)算機(jī)元件或線路故障也頻繁發(fā)生，使得人們更注重網(wǎng)絡(luò)的穩(wěn)定性和實(shí)效性，大家也意識(shí)到了超立方體自身存在的固有缺點(diǎn)，因此超立方體的許多變形網(wǎng)絡(luò)也這樣被提出來(lái)，目的都是為了改進(jìn)超立方體的不足，其中最具代表性的變形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有k元n立方體，它能實(shí)現(xiàn)很多算法從而提供更有效的通信模式，因而k元n立方體的并行算法，路由選擇，連通度，容錯(cuò)性和嵌入路（圈）多路等問(wèn)題就成為了許多學(xué)者關(guān)注的研究點(diǎn),見(jiàn)文獻(xiàn)[1-5].在實(shí)時(shí)系統(tǒng)網(wǎng)絡(luò)中，多條點(diǎn)不交路可以提高網(wǎng)絡(luò)傳輸?shù)膶?shí)效性和穩(wěn)定性，近年來(lái)，學(xué)者在一對(duì)多條不交路和多對(duì)多條不交路覆蓋的方向上研究已經(jīng)獲得了許多有價(jià)值的成就（見(jiàn)文獻(xiàn)[6-13]），但學(xué)者對(duì)這些路徑是否等長(zhǎng)度方面得到成果比較少.討論在邊容錯(cuò)條件下3元n立方體中兩條等長(zhǎng)頂點(diǎn)不交覆蓋路嵌入.將證明下面結(jié)論.

定理1當(dāng)n≥2,邊故障集|F|≤n-2 時(shí)，在中任意三個(gè)頂點(diǎn)x,y1,y2,則在-F中存在兩條內(nèi)部頂點(diǎn)不交的等長(zhǎng)覆蓋路P1=(x,···,y1)和P2=(x,···,y2).

1 預(yù)備知識(shí)和引理

文中的概念和記號(hào)參見(jiàn)文獻(xiàn)[14]，E(G)和V(G)分別代表圖G的邊集和頂點(diǎn)集.P=v0e1v1e2v2…ekvk表示以v0為起點(diǎn)和以vk為終點(diǎn)的路；路P=v0e1v1e2v2…ekvk包含k條邊，稱路P的長(zhǎng)度|P|為k；如果兩條路P1和P2各自包含的邊數(shù)個(gè)數(shù)相等，則稱路P1和P2等長(zhǎng)，記為|P1|=|P2|.對(duì)于故障集F?V(G)∪E(G)且|F|≤k,在G-F中任取兩個(gè)端點(diǎn)x和y，若在G-F中有一條連接x和Qn-F的哈密爾頓路，則稱圖G是k邊(點(diǎn))容錯(cuò)哈密爾頓可跡.給定圖G中m個(gè)源點(diǎn)s1,s2,…,sm和m個(gè)匯點(diǎn)t1,t2,…,tm，若圖有m條內(nèi)部點(diǎn)不交路P1,P2,…,Pm覆蓋圖G的所有頂點(diǎn)，這里Pi=(si,···,ti)，i∈{1,2,…,m}，即V(Pi)∩V(Pj)=?，V(Pi)∪V(Pj)=V(G)，i,j∈{1,2,…,m}，則稱圖G是m條點(diǎn)不交覆蓋路的，若這m條不交路P1,P2,…,Pm長(zhǎng)度都是相等的，則稱G為m條等長(zhǎng)不交覆蓋路的.

2 定理1的證明

證明下面采用歸納法對(duì)n作歸納證明.

情況1若x,y1,y2在Q[0]中.

當(dāng)F0≤n-2，取(w,h)∈F0，在歸納假設(shè)得，在Q[0]-F0+(w,h)中存在兩條內(nèi)部頂點(diǎn)不交的等長(zhǎng)覆蓋路l1=(x,···,y1)和l2=(x,···,y2).若(w,h)∈l1或(w,h)∈l2，則不妨假設(shè)(w,h)∈l1，則在路l1上取邊(w,h)，重新記邊(w,h)=(u,v)，若(w,h)?l1且(w,h)?l2，則在路l1上取一條邊(u,v)，(u1,v1)是(u,v)在Q[1]的對(duì)應(yīng)邊，由引理1得，在Q[1]-F1中存在一條哈密爾頓路l3=(u1,···,v1).在路l2上取一條邊(s,t)，(s2,t2)是(s,t)在Q[2]的對(duì)應(yīng)邊，由引理1得，在Q[2]-F2中存在一條哈密爾頓路l4=(s2,···,t2).令P1=(l1-(u,v))∪(u,u1)∪(v,v1)∪l3，P2=(l2-(s,t))∪(s,s2)∪(t,t2)∪l4,又|P1|=|P2|且V(P1)∪V(P2)=，這里P1連接x和y1，P2連接x和y2.則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求，如圖1所示.

圖1 x,y1,y2在Q[0]中的情況Fig.1 x,y1,y2 in Q[0]

情況2若x,y1在Q[0]中，y2在Q[1]中.

當(dāng)F0≤n-3.由于3n-1＞3，故在Q[0]中存在一點(diǎn)w，使得w≠x≠y1且w在Q[1]的對(duì)應(yīng)點(diǎn)w1≠y2，在歸納假設(shè)得，在Q[0]-F0中存在兩條內(nèi)部頂點(diǎn)不交的等長(zhǎng)覆蓋路l1=(x,···,y1)和l2=(x,···,w).在路l1上取一條邊(s,t)，(s2,t2)是(s,t)在Q[2]的對(duì)應(yīng)邊，由引理1 得，在Q[2]-F2中有一條哈密爾頓路l3=(s2,···,t2)，由引理1 得，在Q[1]-F1中存在一條哈密爾頓路l4=(w1,···,y2).令P1=(l1-(s,t))∪(s,s2)∪(t,t2)∪l3，P2=l2∪(w,w1)∪l4,又V(P1)∪V(P2)=且|P1|=|P2|，這里P1連接x和y1，P2連接x和y2.則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求，如圖2所示.

圖2 F0≤n-3的情況Fig.2 The case if F0≤n-3

當(dāng)F0=n-2.由引理1得，在Q[0]-F0中有一條哈密爾頓路l1連接x和y1，在路l1上存在一條邊(s,t)將路l1分成l2=(x,···,s)和l3=(t,···,y1)，使得|l2|=(3n-1-1)/2和|l3|=(3n-1-1)/2-1.設(shè)x和t在Q[2]的對(duì)應(yīng)點(diǎn)分別為x2和t2，由引理1得，在Q[2]中存在一條哈密爾頓路l4=(x2,···,t2).若s在Q[1]的對(duì)應(yīng)點(diǎn)s1≠y2，由引理1得，在Q[1]中存在一條哈密爾頓路l5=(s1,···,y2)，令P1=(x,x2)∪l4∪(t2,t)∪l3，P2=l2∪(s,s1)∪l5,又V(P1)∪V(P2)=且|P1|=|P2|，這里P1=(x,···,y1)，P2=(x,···,y2).則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求，如圖3所示.若s在Q[1]的對(duì)應(yīng)點(diǎn)s1=y2，在l2上取一條邊(u,v)，設(shè)(u1,v1)是(u,v)在Q[1]的對(duì)應(yīng)邊，由引理1得，在Q[1]-y2中存在哈密爾頓路l6=(u1,···,v1).令P2=(l2-(u,v))∪(u,u1)∪l6∪(v,v1)∪(s1,y2)，P1=(x,x2)∪l4∪(t2,t)∪l3.則上述兩條等長(zhǎng)不交路P1和P2滿足定理1，如圖4所示.

圖3 F0=n-2,s1≠y2 的情況Fig.3 The case of F0=n-2,s1≠y2

圖4 F0=n-2,s1=y2的情況Fig.4 The case of F0=n-2,s1=y2

情況3若x在Q[0]中，y1，y2在Q[1]中.

當(dāng)1 ≤F0≤n-2.因?yàn)镕1≤n-3，在Q[1]中取一點(diǎn)s，使得s≠y1≠y2且s在Q[0]的對(duì)應(yīng)點(diǎn)s0≠x，在歸納假設(shè)得，在Q[1]-F1中存在兩條內(nèi)部頂點(diǎn)不交的等長(zhǎng)覆蓋路l1=(s,w,···,y1)和l2=(s,h,···,y2)，由引理1 得，在Q[0]-F0中存在一條哈密爾頓路l3=(x,···,s0).設(shè)x在Q[2]的對(duì)應(yīng)點(diǎn)x2，設(shè)w和h在Q[2]的對(duì)應(yīng)點(diǎn)分別為w2和h2，則有w2≠x2或h2≠x2，不妨設(shè)h2≠x2，由引理1得，在Q[2]-F2中存在一條哈密爾頓路l4=(h2,···,x2).令P1=l3+(s0,s)∪l1，P2=(x,x2)∪l4∪(h2,h)∪(l2-(s,h)),又|P1|=|P2|，則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求，如圖5所示.

圖5 1≤F0≤n-2的情況Fig.5 The case of 1 ≤F0≤n-2

當(dāng)F0=0.因?yàn)镕1≤n-2，由引理1得，在Q[1]-F1中存在一條哈密爾頓路l1連接y1和y2.在路l1上存在一條邊(s,t)將路l1分成l2=(y1,···,s)和l3=(t,···,y2)，使得|l2|=a和|l3|=3n-1-1-a，這里1≤a≤3n-1-2.設(shè)(s,t)在Q[2]的對(duì)應(yīng)邊為(s2,t2)，因?yàn)镕2≤n-2，由引理1 得，在Q[2]-F2中有哈密爾頓路l4=(s2,···,t2).在路l4上存在一條邊(u,v)將路l4分成l5=(s2,···,u)和l6=(t2,···,v)，使得|l5|=3n-1-1-a和|l6|=a，這里1 ≤a≤3n-1-2.因a的取值有3n-1-2 種，所以必定存在u0≠v0≠x，這里(u0,v0)是(u,v)在Q[0]的對(duì)應(yīng)邊，由歸納假設(shè)得，在Q[0]中存在兩條點(diǎn)不交的等長(zhǎng)覆蓋路l7=(x,···,u0) 和l8=(x,···,v0).令P1=l7∪(u0,u)∪l5∪(s2,s)∪l2，P2=l8∪(v0,v)∪l6∪(t2,t)∪l3,又|P1|=|P2|，則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求，如圖6所示.

圖6 F0=0的情況Fig.6 The case of F0=0

情況4若x在Q[0]中，y1在Q[1]中，y2在Q[2]中.

當(dāng)F0≤n-2.由引理2，在Q[0]-F0中存在一條哈密爾頓圈C=(x,···,s,t,···,x)，因?yàn)閨C|=3n-1是奇數(shù)，所以圈C中存在一條邊(s,t)使得(x,···,s)=l1和(x,···,t)=l2長(zhǎng)度相等，假設(shè)s在Q[1]的對(duì)應(yīng)點(diǎn)s1，t在Q[2]的對(duì)應(yīng)點(diǎn)t2，若s1≠y1且t2≠y2，由引理1得，在Q[1]-F1中存在一條哈密爾頓路l3=(s1,···,y1).由引理1得，在Q[2]-F2中存在一條哈密爾頓路l4=(t2,···,y2).令P1=l1∪(s,s1)∪l3，P2=l2∪(t,t2)∪l4,又|P1|=|P2|且V(P1)∪V(P2)=，這里P1連接x和y1，P2連接x和y2.則上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求.若s1≠y1且t2=y2（或s1=y1且t2≠y2），不妨設(shè)s1≠y1且t2=y2，由引理1 得，在Q[1]-F1中存在一條哈密爾頓路l5=(s1,···,y1).在路l2中取一條邊(u,v)，使得u2≠v2≠y2，這里(u2,v2)是(u,v)在Q[2]的對(duì)應(yīng)邊，由引理1得，在Q[2]-F2-y2中存在一條哈密爾頓路l6=(u2,···,v2).則如圖7 所示上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求.若s1=y1且t2=y2，在路l1中取一條邊(w,h)，使得w1≠h1≠y1，這里(w1,h1)是(w,h)在Q[1]的對(duì)應(yīng)邊，由引理1 得，在Q[1]-F1-y1中存在一條哈密爾頓路l7=(w1,···,h1).在路l2中取一條邊(u,v)，使得u2≠v2≠y2，這里(u2,v2)是(u,v)在Q[2]的對(duì)應(yīng)邊，由引理1 得，在Q[2]-F2-y2中存在一條哈密爾頓路l8=(u2,···,v2).則如圖8所示上述兩條等長(zhǎng)不交路P1和P2滿足定理1要求.

圖7 s1≠y1且t2=y2的情況Fig.7 The case of s1≠y1 and t2=y2

圖8 情況4 s1=y1且t2=y2Fig.8 The case of s1=y1 and t2=y2

證畢.

3 展望

文中研究了邊故障3 元n立方體中存在兩條等長(zhǎng)覆蓋路問(wèn)題，定理1 故障邊數(shù)|F|≤n-2 是否已經(jīng)達(dá)到最佳上界?網(wǎng)絡(luò)系統(tǒng)中結(jié)點(diǎn)故障的出現(xiàn)必然影響系統(tǒng)的直徑，若3 元n立方體中故障出現(xiàn)在結(jié)點(diǎn)時(shí)，在3元n立方體中刪除故障結(jié)點(diǎn)后是否依然存在兩條等長(zhǎng)覆蓋路等問(wèn)題都值得后續(xù)加以研究.