5元n立方體中指定三條點(diǎn)不交覆蓋路

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

(漳州職業(yè)技術(shù)學(xué)院通識(shí)教育學(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(shí)效性和穩(wěn)定性.學(xué)者們開始意識(shí)到超立方體存在的不足,比如直徑大、通信步數(shù)過(guò)長(zhǎng)等.為了改進(jìn)這些不足,科學(xué)家們提出了許多變形網(wǎng)絡(luò),例如折疊立方體、平衡立方體、交叉立方體、k元n立方體等.其中k元n立方體是最具代表性的變形網(wǎng)絡(luò)之一,它能實(shí)現(xiàn)很多并行算法,從而提供更可靠的網(wǎng)絡(luò)互連模式,因此k元n立方體的嵌入路(圈)路、容錯(cuò)直徑、路由選擇、Menger數(shù)和通信模式(特別是一對(duì)多)等問(wèn)題就成為國(guó)內(nèi)外許多學(xué)者的研究焦點(diǎn)[1-5].在實(shí)時(shí)網(wǎng)絡(luò)系統(tǒng)中,點(diǎn)不交路能降低數(shù)據(jù)傳輸擁堵情況,減少數(shù)據(jù)丟失現(xiàn)象,從而提高數(shù)據(jù)傳輸效率.近幾年來(lái),學(xué)者在(容錯(cuò))一對(duì)多條不交路和多對(duì)多條不交路覆蓋的方向上獲得了很多有效成果[6-13],但大部分成果是多對(duì)多條不交路覆蓋,對(duì)于一對(duì)多的成果研究相對(duì)較少.本文討論在5元n立方體中一對(duì)三條內(nèi)部頂點(diǎn)不交覆蓋路嵌入.

1 主要定理

本文的圖論概念和記號(hào)見(jiàn)參考文獻(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))容錯(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)不交覆蓋路的.

引理2[3]當(dāng)k1,k2是奇數(shù),k1,k2≥5時(shí),二維環(huán)面網(wǎng)絡(luò)Torus(k1,k2)存在一對(duì)三條內(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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]的對(duì)應(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é)語(yǔ)

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