佘卫强

(漳州职业技术学院通识教育学院,福建 漳州 363000)

0 引言

1962年密歇根大学的Squire和Palais提出超立方体计算机的构想,从此超立方体就以优异的性质在并行算法处理和并行计算系统中成为最常用的网络结构,但随着网络系统发展日益庞大复杂,网络的元件或线路也经常发生故障,使得用户更加注重网络传输的时效性和稳定性.学者们开始意识到超立方体存在的不足,比如直径大、通信步数过长等.为了改进这些不足,科学家们提出了许多变形网络,例如折叠立方体、平衡立方体、交叉立方体、k元n立方体等.其中k元n立方体是最具代表性的变形网络之一,它能实现很多并行算法,从而提供更可靠的网络互连模式,因此k元n立方体的嵌入路(圈)路、容错直径、路由选择、Menger数和通信模式(特别是一对多)等问题就成为国内外许多学者的研究焦点[1-5].在实时网络系统中,点不交路能降低数据传输拥堵情况,减少数据丢失现象,从而提高数据传输效率.近几年来,学者在(容错)一对多条不交路和多对多条不交路覆盖的方向上获得了很多有效成果[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时,二维环面网络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),然后适当考虑故障边数或故障点数所能达到的最佳上界是否会影响本结论.由于篇幅有限,对于类似问题将进行后续研究.