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

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

0 引言

1962年密歇根大學(xué)的Squire和Palais提出超立方體計(jì)算機(jī)的構(gòu)想,從此超立方體就以優(yōu)異的性質(zhì)在并行算法處理和并行計(jì)算系統(tǒng)中成為最常用的網(wǎng)絡(luò)結(jié)構(gòu),但隨著網(wǎng)絡(luò)系統(tǒng)發(fā)展日益龐大復(fù)雜,網(wǎng)絡(luò)的元件或線路也經(jīng)常發(fā)生故障,使得用戶更加注重網(wǎng)絡(luò)傳輸?shù)臅r效性和穩(wěn)定性.學(xué)者們開始意識到超立方體存在的不足,比如直徑大、通信步數(shù)過長等.為了改進(jìn)這些不足,科學(xué)家們提出了許多變形網(wǎng)絡(luò),例如折疊立方體、平衡立方體、交叉立方體、k元n立方體等.其中k元n立方體是最具代表性的變形網(wǎng)絡(luò)之一,它能實(shí)現(xiàn)很多并行算法,從而提供更可靠的網(wǎng)絡(luò)互連模式,因此k元n立方體的嵌入路(圈)路、容錯直徑、路由選擇、Menger數(shù)和通信模式(特別是一對多)等問題就成為國內(nèi)外許多學(xué)者的研究焦點(diǎn)[1-5].在實(shí)時網(wǎng)絡(luò)系統(tǒng)中,點(diǎn)不交路能降低數(shù)據(jù)傳輸擁堵情況,減少數(shù)據(jù)丟失現(xiàn)象,從而提高數(shù)據(jù)傳輸效率.近幾年來,學(xué)者在(容錯)一對多條不交路和多對多條不交路覆蓋的方向上獲得了很多有效成果[6-13],但大部分成果是多對多條不交路覆蓋,對于一對多的成果研究相對較少.本文討論在5元n立方體中一對三條內(nèi)部頂點(diǎn)不交覆蓋路嵌入.

1 主要定理

本文的圖論概念和記號見參考文獻(xiàn)[14],V(G)和E(G)分別表示圖G的點(diǎn)集和邊集;以v0為起點(diǎn)、vk為終點(diǎn)的路記為P=v0e1v1e2v2…ekvk;在G-F中任取兩點(diǎn)x和y,設(shè)故障集F?V(G)∪E(G),且|F|≤k,若在G-F中存在一條哈密爾頓路連接P=(x,…,y),則稱圖G是k邊(點(diǎn))容錯哈密爾頓可跡;指定圖G中m個起點(diǎn)s1,s2,…,sm和m個終點(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)不交覆蓋路的.

引理2[3]當(dāng)k1,k2是奇數(shù),k1,k2≥5時,二維環(huán)面網(wǎng)絡(luò)Torus(k1,k2)存在一對三條內(nèi)部點(diǎn)不交覆蓋路.

引理3[15]設(shè)i≤k≤j,任取x∈V(Q[i]),y∈V(Q[k]),則Q[i,j]中存在一條哈密爾頓路P=(x,…,y).

2 定理的證明

情況1 若x,y1,y2,y3∈V(Q[0]).

由歸納假設(shè)得到,在Q[0]中存在三條內(nèi)部頂點(diǎn)不交的覆蓋路l1=(x,…,y1),l2=(x,…,y2),l3=(x,…,y3).則不妨假設(shè)|l1|≥|l2|≥|l3|,則在路l1上取邊(u,v),設(shè)(u1,v1)是(u,v)在Q[1]的對應(yīng)邊,由引理3,在Q[1,4]中存在一條哈密爾頓路l4=(u1,…,v1).令P1=(l1-(u,v))∪(u,u1)∪(v,v1)∪l4,P2=l2,P3=l3,則上述三條不交路P1,P2,P3滿足定理1要求.

情況2 若x,y1,y2∈V(Q[0]),y3∈V(Q[i]),i∈{1,2,3,4}.

在Q[0]中取一點(diǎn)s,使得s在Q[1]的對應(yīng)點(diǎn)s1≠y3,由歸納假設(shè)得到,在Q[0]中存在三條內(nèi)部頂點(diǎn)不交的覆蓋路l1=(x,…,y1),l2=(x,…,y2),l3=(x,…,s).由引理3可知,在Q[1,4]中存在一條哈密爾頓路l4=(s1,…,y3).令P1=l1,P2=l2,P3=l3∪(s,s1)∪l4,則上述三條不交路P1,P2,P3滿足定理1要求,如圖1所示.

圖1 x,y1,y2∈V(Q[0]),y3∈V(Q[i])的情況

圖2 x,y1∈V(Q[0])的情況

情況3 若x,y1∈V(Q[0]),y2,y3∈V(Q[i]),i∈{1,2,3,4},或若x,y1∈V(Q[0]),y2∈V(Q[i]),y3∈V(Q[j]),i≠j∈{1,2,3,4}.

由引理3可得,在Q[1,4]中存在一條哈密爾頓路l1=(y2,…,y3).在路l1中取一邊(u,v),使得(u,v)∈E(Q[1]),且u0≠v0≠x≠y1,這里(u0,v0)是(u,v)在Q[0]的對應(yīng)邊,邊(u,v)將路l1分成兩條路l2=(y2,…,u)和l3=(y3,…,v).由歸納假設(shè)得到,在Q[0]中存在三條內(nèi)部頂點(diǎn)不交的覆蓋路l4=(x,…,y1),l5=(x,…,u0),l6=(x,…,v0).令P1=l4,P2=l5∪(u0,u)∪l2,P3=l6∪(v0,v)∪l3,則上述三條不交路P1,P2,P3滿足定理1要求,如圖2所示.

情況4 若x∈V(Q[0]),y1,y2,y3∈V(Q[i]),i∈{1,4}.

圖3 x∈V(Q[0]),y1,y2,y3∈V(Q[i]),i∈{1,4}的情況

情況5 若x∈V(Q[0]),y1,y2,y3∈V(Q[i]),i∈{2,3}.

圖4 x∈V(Q[0]),y1,y2,y3∈V(Q[i]),i∈{2,3}的情況

情況6 若x∈V(Q[0]),y1,y2∈V(Q[1]),y3∈V(Q[i]),i∈{2,3,4}.

由引理1可得,在Q[1]中存在一條哈密爾頓路l1=(y1,…,y2).因?yàn)?n-1-1>1,所以在路l1中存在一邊(u,v),使得u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應(yīng)邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因?yàn)?n-1-3>1,所以在Q[0]中存在一點(diǎn)s,使得s≠x≠u0≠v0且s4≠y3,這里s4是s在Q[4]的對應(yīng)點(diǎn),由歸納假設(shè)可得,在Q[0]中存在三條內(nèi)部頂點(diǎn)不交的覆蓋路l4=(x,…,u0),l5=(x,…,v0),l6=(x,…,s).根據(jù)引理3,在Q[2,4]中存在一條哈密爾頓路l7=(s4,…,y3).令P1=l4∪(u0,u)∪l2,P2=l5∪(v0,v)∪l3,P3=l6∪(s,s4)∪l7,則上述三條不交路P1,P2,P3滿足定理1要求,如圖5所示.

圖5 x∈V(Q[0]),y1,y2∈V(Q[1]),y3∈V(Q[i]),i∈{2,3,4}的情況

情況7 若x∈V(Q[0]),y1,y2∈V(Q[2]),y3∈V(Q[1]).

由引理3可得,在Q[2,4]中存在一條哈密爾頓路l1=(y1,…,y2).因?yàn)?×5n-1-1>1,所以在路l1中存在一邊(u,v),使得(u,v)∈E(Q[4]),且u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應(yīng)邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因?yàn)?n-1-3>1,所以在Q[0]中存在一點(diǎn)s,使得s≠x≠u0≠v0且s1≠y3,這里s1是s在Q[1]的對應(yīng)點(diǎn),由歸納假設(shè)可得,在Q[0]中存在三條內(nèi)部頂點(diǎn)不交的覆蓋路l4=(x,…,u0),l5=(x,…,v0),l6=(x,…,s).由引理3可得,在Q[1]中存在一條哈密爾頓路l7=(s1,…,y3).令P1=l4∪(u0,u)∪l2,P2=l5∪(v0,v)∪l3,P3=l6∪(s,s1)∪l7,則上述三條不交路P1,P2,P3滿足定理1要求,如圖6所示.

圖6 x∈V(Q[0]),y1,y2∈V(Q[2]),y3∈V(Q[1])的情況

情況8 若x∈V(Q[0]),y1,y2∈V(Q[2]),y3∈V(Q[i]),i∈{3,4}.

由引理3可得,在Q[1,2]中存在一條哈密爾頓路l1=(y1,…,y2).在路l1中取一邊(u,v),使得(u,v)∈E(Q[1])且u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應(yīng)邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).在Q[i]中取一點(diǎn)s,使得s≠u0≠v0≠x且s4≠y3,這里s4是s在Q[4]的對應(yīng)點(diǎn),由歸納假設(shè)可得,在Q[0]中有三條點(diǎn)不交的覆蓋路l4=(x,…,u0),l5=(x,…,v0),l6=(x,…,s).由引理3可得,在Q[3,4]中有一條哈密爾頓路l7=(s4,…,y3).令P1=l4∪(u0,u)∪l2,P2=l5∪(v0,v)∪l3,P3=l6∪(s,s4)∪l7,則上述三條不交路P1,P2,P3滿足定理1要求.

情況9 若x∈V(Q[0]),y1∈V(Q[i]),y2∈V(Q[j]),y3∈V(Q[k]),1≤i≠j≠k≤4.

因?yàn)閥1,y2,y3有一點(diǎn)在Q[1]或Q[4]中,不妨設(shè)y3∈V(Q[1]),由引理3可得,在Q[2,4]中存在一條哈密爾頓路l1=(y1,…,y2).在路l1中取一邊(u,v),使得(u,v)∈E(Q[4]),且u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應(yīng)邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因?yàn)?n-1-3>1,所以在Q[0]中存在一點(diǎn)s,使得s≠x≠u0≠v0且s1≠y3,這里s1是s在Q[1]的對應(yīng)點(diǎn),由歸納假設(shè)可得,在Q[0]中有三條內(nèi)部點(diǎn)不交的覆蓋路l4=(x,…,u0),l5=(x,…,v0),l6=(x,…,s).由引理3可得,在Q[1]中存在一條哈密爾頓路l7=(s1,…,y3).令P1=l4∪(u0,u)∪l2,P2=l5∪(v0,v)∪l3,P3=l6∪(s,s1)∪l7,則上述三條不交路P1,P2,P3滿足定理1要求.

3 結(jié)語

本文研究了5元n立方體中存在一對多條不交覆蓋路問題.實(shí)際上本文結(jié)論可以推廣到更高階的k元n立方體(k>5),然后適當(dāng)考慮故障邊數(shù)或故障點(diǎn)數(shù)所能達(dá)到的最佳上界是否會影響本結(jié)論.由于篇幅有限,對于類似問題將進(jìn)行后續(xù)研究.