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

佘衛(wèi)強

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

0 引言

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

1 主要定理

本文的圖論概念和記號見參考文獻[14],V(G)和E(G)分別表示圖G的點集和邊集;以v0為起點、vk為終點的路記為P=v0e1v1e2v2…ekvk;在G-F中任取兩點x和y,設故障集F?V(G)∪E(G),且|F|≤k,若在G-F中存在一條哈密爾頓路連接P=(x,…,y),則稱圖G是k邊(點)容錯哈密爾頓可跡;指定圖G中m個起點s1,s2,…,sm和m個終點t1,t2,…,tm,若圖有m條內部頂點不交路P1,P2,…,Pm覆蓋G中的所有頂點,這里Pi=(si,…,ti),i∈{1,2,…,m},即V(Pi)∩V(Pj)=?,V(Pi)∪V(Pj)=V(G),i≠j∈{1,2,…,m},則稱圖G是m條點不交覆蓋路的.

引理2[3]當k1,k2是奇數,k1,k2≥5時,二維環(huán)面網絡Torus(k1,k2)存在一對三條內部點不交覆蓋路.

引理3[15]設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]).

由歸納假設得到,在Q[0]中存在三條內部頂點不交的覆蓋路l1=(x,…,y1),l2=(x,…,y2),l3=(x,…,y3).則不妨假設|l1|≥|l2|≥|l3|,則在路l1上取邊(u,v),設(u1,v1)是(u,v)在Q[1]的對應邊,由引理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]中取一點s,使得s在Q[1]的對應點s1≠y3,由歸納假設得到,在Q[0]中存在三條內部頂點不交的覆蓋路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]的對應邊,邊(u,v)將路l1分成兩條路l2=(y2,…,u)和l3=(y3,…,v).由歸納假設得到,在Q[0]中存在三條內部頂點不交的覆蓋路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).因為5n-1-1>1,所以在路l1中存在一邊(u,v),使得u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因為5n-1-3>1,所以在Q[0]中存在一點s,使得s≠x≠u0≠v0且s4≠y3,這里s4是s在Q[4]的對應點,由歸納假設可得,在Q[0]中存在三條內部頂點不交的覆蓋路l4=(x,…,u0),l5=(x,…,v0),l6=(x,…,s).根據引理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).因為3×5n-1-1>1,所以在路l1中存在一邊(u,v),使得(u,v)∈E(Q[4]),且u0≠v0≠x,這里(u0,v0)是(u,v)在Q[0]的對應邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因為5n-1-3>1,所以在Q[0]中存在一點s,使得s≠x≠u0≠v0且s1≠y3,這里s1是s在Q[1]的對應點,由歸納假設可得,在Q[0]中存在三條內部頂點不交的覆蓋路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]的對應邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).在Q[i]中取一點s,使得s≠u0≠v0≠x且s4≠y3,這里s4是s在Q[4]的對應點,由歸納假設可得,在Q[0]中有三條點不交的覆蓋路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.

因為y1,y2,y3有一點在Q[1]或Q[4]中,不妨設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]的對應邊,邊(u,v)將路l1分成兩條路l2=(y1,…,u)和l3=(y2,…,v).因為5n-1-3>1,所以在Q[0]中存在一點s,使得s≠x≠u0≠v0且s1≠y3,這里s1是s在Q[1]的對應點,由歸納假設可得,在Q[0]中有三條內部點不交的覆蓋路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 結語

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