邊故障5元n立方體的兩條不交覆蓋路

管文慧，李 晶，高曉慧

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

?

邊故障5元n立方體的兩條不交覆蓋路

管文慧，李 晶，高曉慧

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

互連網(wǎng)絡(luò)；5元n立方體；不交路覆蓋

1 預(yù)備知識(shí)

Q[j]和Q[j+1]稱為相鄰子立方體，對(duì)于Q[j]中的任一頂點(diǎn)xj，在Q[j-1]和Q[j+1]中分別有一個(gè)對(duì)應(yīng)點(diǎn)，記為xj-1和xj+1.對(duì)任意兩個(gè)整數(shù)p,q∈[0,k]，且p

下面給出證明中將用到的引理。

引理2[5]設(shè)m≥3，奇數(shù)n≥3，則Torus(m,n)有兩條點(diǎn)不交的覆蓋路連接圖中任意兩對(duì)頂點(diǎ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例異位妊娠患者為研究對(duì)象,隨機(jī)分為兩組,各25例,對(duì)照組接受經(jīng)腹彩超檢測(cè),年齡21~44歲,平均年齡(27.5±3.5)歲,停經(jīng)時(shí)間30~120d,平均停經(jīng)時(shí)間(49.5±2.5)d;觀察組接受經(jīng)陰道超聲檢測(cè),年齡22~45歲,平均年齡(28.5±3.5)歲,停經(jīng)時(shí)間31~120d,平均停經(jīng)時(shí)間(50.0±2.5)d;兩組患者均已通過(guò)相關(guān)檢測(cè),符合檢測(cè)標(biāo)準(zhǔn),無(wú)超聲、彩超不適者,均有明顯停經(jīng)史,HCG顯示陽(yáng)性,排除其他傳染疾病,年齡、停經(jīng)時(shí)間等方面經(jīng)統(tǒng)計(jì)學(xué)分析,無(wú)顯著性差異,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] 佘衛(wèi)強(qiáng)，方來(lái)金.邊故障超立方體中兩條無(wú)故障點(diǎn)不交路[J].漳州師范學(xué)院學(xué)報(bào)，2009(1)：7-9.

[3] 佘衛(wèi)強(qiáng).邊故障3-aryn立方體中兩條無(wú)故障點(diǎn)不交路[J].漳州師范學(xué)院學(xué)報(bào)，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

國(guó)家自然科學(xué)基金(61303020)；山西省青年自然科學(xué)基金(2013021018-3)；山西省高等學(xué)校優(yōu)秀青年學(xué)術(shù)帶頭人支持計(jì)劃(20151005)

管文慧(1990-)，女，碩士研究生，主要研究方向?yàn)閳D論及泛函分析。

1673-2057(2015)06-0470-05

O157.5

A

10.3969/j.issn.1673-2057.2015.06.012