边故障3元n立方体中的一对二点不交路覆盖①

佘卫强

(漳州职业技术学院公共教学部，福建 漳州 363000 )

0 引 言

1962年研究人员提出超立方体计算机的设想，1977年超立方体并行处理机问世， 随后出现很多基于超立方体网络的超级计算机投入到商业运行中. 虽然超立方体网络有许多优良的性质也已取得了很多研究成果[1～ 2]，但它还是有很多缺点，为了改进超立方体的缺点，许多专家学者提出超立方体的某些变形网络，例如增广立方体、k-ary n-立方体等[3～ 4].如今互连网发展迅速，人们对网络信息传递的有效性要求越来越高，因此某些变形网络的性质如容错路(圈)和多路等问题自然就成了研究热点.变形网络中k元n立方体具有直径小，可迁的,高连通性和高容错性等优良性质.3元n立方体的这些优良性质使得它在大规模并行处理系统中具有很强竞争力.近几年来，学者对3元n立方体(容错)路的研究已得到了许多的成果[6～8]，本文研究在3元n立方体中的不匹配一对二不交路覆盖问题得到：

定理1当n≥2，边故障|F|2n-3时，在中任取3个顶点x0,y1,y2，则在中有两条内部不交路P1,P2，使得这里P1连接x0和y1，P2连接x0和y2，而且边故障|F|2n-3为最优上界.

1 基本定义

2 定理1证明

对n作归纳法证明.

给定S=(s1,s2,…,sk)源点集，T=(t1,t2,…,tk)汇点集，若图G有k条点不交路P1,P2,…,Pk使得

当n=2时,显然定理1成立.对3k

2.1 若 x0,y1,y2在Q[0]中

2.1.1 若|F0|=2n-4

连接x0和y2.

2.1.2 若|F0|2n-5

当|F1|2n-5时，由归纳假设得，在Q[0]-F1中有两条内部不交路l0连接x0和连x0和y2.因不妨设在中有边(s0,t0)使得和都无故障.因为|F1|2n-5，由引理1得，在Q[1]-F1中有哈密尔顿路l1连接和在l1中取一条边(u1,v1)使得和都无故障，因为|F2|2n-5，由引理1得，在Q[2]-F2中有一条哈密尔顿路l2连接和故在中有满足定理的两条内部不交路P0=l0和

2.2 若x0,y1∈Q[0]，y2∈Q[1]

2.2.1 若|F0|=2n-4

2.2.2 若|F1|=2n-4

2.2.3 若|Fi|2n-5，i∈{0,1}或1|F2|2n-4

因|F2|2n-42(n-1)-2，由引理1得，在Q[2]-F2中有存在一条哈密尔顿圈C2，因|C2|-|F|≥3n-1-(2n-3)>4，故C2有边(s2,t2)使得且由引理1得，在Q[1]中有哈密尔顿路l1连接和y2.由归纳假设得，在Q[0]中有两条内部不交路l0连接x0和连接x0和故在中有满足定理的两条内部不交路P0=l0和

2.3 若x0∈Q[0]，y1,y2∈Q[1]

2.3.1 若|F0|=2n-4

因|F0|2(n-1)-2，由引理1得，Q[0]-F0中有哈密尔顿圈C0，在C0中有边(s0,t0)使得且由引理1得，在Q[2]中有哈密尔顿路l2连接和因为|l2|-|F|≥3n-1-(2n-3)>4，故在l2中有一边(u2,v2)使得且由引理2得，在Q[1]中有两条内部不交路l1连接和连接和y2.故在中有满足定理的两条内部不交路和

2.3.2 若|F1|=2n-4

2.3.3 若|F2|=2n-4

因|F2|2(n-1)-2，由引理1得，在Q[2]-F2中有哈密尔顿圈C2，在C2中取一条边(s2,t2)使得且由归纳假设得，在Q[0]中有两条内部不交路l0连接x0和连接x0和因|C2|-|F|≥3n-1-(2n-3)>4，故在C2中有边(u2,v2)使得且由引理2得，在Q[1]中有两条内部不交路l1连接和y1；l1′连接和y2.故在中有满足定理的两条内部不交路和

因|F1|2(n-1)-3，由引理1得，在Q[1]-F1中存在一条哈密尔顿路l1连接y1和y2.因|l1|-|F|≥3n-1-(2n-3)>2，故l1中有边(s1,t1)，使得和都无故障.由|F2|2(n-1)-3，由引理1得，在Q[2]-F2中有哈密尔顿路l2连接和在l2中取一边(u2,v2)使得和无故障且由|F0|2(n-1)-3，由归纳假设得，在Q[0]-F0中有两条内部不交路l0连接x0和连接x0和故在中有满足定理的两条内部不交路和

2.4 若x0∈Q[0]，y1∈Q[1]，y2∈Q[2]

不妨设|F2||F1||F0|2(n-1)-2，由引理1得，在Q[0]-F0中存在一条哈密尔顿圈C0.因|l0|-|F|≥3n-1-(2n-3)>4，故C0有边(s0,t0)，使得和都无故障且因|F1|2(n-1)-3，由引理1得，在Q[1]-F1中有哈密尔顿路l1连接y1和因|F2|2(n-1)-3，由引理1得，Q[2]-F2中有哈密尔顿路l2连y2和故中有满足定理的两条内部不交路和

定理1归纳法证毕.

3 结 语

定理中的边故障|F|2n-3是最优上界.因为中的每个顶点度数都是2n，当与点x0关联的2n-2条边为故障边，若剩余两条与x0关联边为(x0,y1)和(x0,y2)时，则中没有满足定理的两条内部不交路P0连接x0和y1；P1连接x0和y2.