边故障5元n立方体的两条不交覆盖路

管文慧，李 晶，高晓慧

(太原科技大学应用科学学院，太原 030024)



边故障5元n立方体的两条不交覆盖路

管文慧，李 晶，高晓慧

(太原科技大学应用科学学院，太原 030024)

互连网络；5元n立方体；不交路覆盖

1 预备知识

Q[j]和Q[j+1]称为相邻子立方体，对于Q[j]中的任一顶点xj，在Q[j-1]和Q[j+1]中分别有一个对应点，记为xj-1和xj+1.对任意两个整数p,q∈[0,k]，且p

下面给出证明中将用到的引理。

引理2[5]设m≥3，奇数n≥3，则Torus(m,n)有两条点不交的覆盖路连接图中任意两对顶点。

2 定理1证明

情形1a,b,c,d∈V(Q[0]).

图1 情形1Fig.1 Case 1

情形2a,b,c∈V(Q[0])，d∈V(Q[r])(r=1,2,3,4).

选取我院2017年1月~2018年1月收治的50例异位妊娠患者为研究对象,随机分为两组,各25例,对照组接受经腹彩超检测,年龄21~44岁,平均年龄(27.5±3.5)岁,停经时间30~120d,平均停经时间(49.5±2.5)d;观察组接受经阴道超声检测,年龄22~45岁,平均年龄(28.5±3.5)岁,停经时间31~120d,平均停经时间(50.0±2.5)d;两组患者均已通过相关检测,符合检测标准,无超声、彩超不适者,均有明显停经史,HCG显示阳性,排除其他传染疾病,年龄、停经时间等方面经统计学分析,无显著性差异,P>0.05,有可比性。

情形2.1.1 (t0,t1)∈F，则(t0,t4)∉F.

图2 情形2.1.1Fig.2 Case 2.1.1

情形2.1.2 (t0,t4)∈F，则(t0,t1)∉F.

若t1≠d，由引理3得，Q[1,4]存在一条Hamilton路P[t1,d]，令P2[c,d]=P[c,t0]∪(t0,t1)∪P[t1,d](如图3(a)所示).

图3 情形2.1.2Fig.3 Case 2.1.2

图4 情形2.2Fig.4 Case 2.2

情形4a,b∈V(Q[0])，c∈V(Q[r])，d∈V(Q[l])(0

图5 情形3Fig.5 Case 3

图6 情形4Fig.6 Case 4

情形5a,c∈V(Q[0])，b∈V(Q[r])，d∈V(Q[l])(0

图7 情形5Fig.7 Case 5

情形6a∈V(Q[r])，b∈V(Q[s])，c∈V(Q[t])，d∈V(Q[l]).

情形6.1 0≤r

情形6.2 0≤t

图8 情形6.2Fig.8 Case 6.2

[1] RAK T DVO.Hamiltonian cycles with prescribed edges in hypercubes[J].SIAM J Discrete Math，2005，19：135-144.

[2] 佘卫强，方来金.边故障超立方体中两条无故障点不交路[J].漳州师范学院学报，2009(1)：7-9.

[3] 佘卫强.边故障3-aryn立方体中两条无故障点不交路[J].漳州师范学院学报，2010(3)：6-12.

[4] BOSE B，BROEG B，KWON Y.Lee distance and topological properties of k-ary n-cube[J].IEEE Transaction on Computers，1995，44(8)：1021-1030.

[5] JUNG-HEURN PARK.Many-to-Many Disjoint Path covers in two-dimensional Tori[J].Journal of KIISE，2011，38(1)：42-48.

[6] LIN SHANGWEI，WANG SHIYING.Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements[J].Discrete Applied Mathematics，2011，159：212-223.

2-Disjoint Path Covers in 5-aryn-cubes with Fault Edges

GUAN Wen-hui，LI Jing，GAO Xiao-hui

(Taiyuan University of Science and Technology，Taiyuan 030024，China)

The paper studies the problem of 2-disjoint paths cover of 5-ary n-cube.LetFbe any subset of edges withF≤2n-4，the following result is obtained.Assuming thata,b,canddare arbitrarily four distinct vertices inQ5n，there exist two fault-free vertex-disjoint pathsP1betweenaandbandP2betweencand indsuch that cover ofQ5n.

interconnection network，5-aryn-cube，disjoint paths cover

2015-04-14

国家自然科学基金(61303020)；山西省青年自然科学基金(2013021018-3)；山西省高等学校优秀青年学术带头人支持计划(20151005)

管文慧(1990-)，女，硕士研究生，主要研究方向为图论及泛函分析。

1673-2057(2015)06-0470-05

O157.5

A

10.3969/j.issn.1673-2057.2015.06.012