邊故障3元n立方體中的一對(duì)二點(diǎn)不交路覆蓋①

佘衛(wèi)強(qiáng)

(漳州職業(yè)技術(shù)學(xué)院公共教學(xué)部，福建 漳州 363000 )

0 引 言

1962年研究人員提出超立方體計(jì)算機(jī)的設(shè)想，1977年超立方體并行處理機(jī)問(wèn)世， 隨后出現(xiàn)很多基于超立方體網(wǎng)絡(luò)的超級(jí)計(jì)算機(jī)投入到商業(yè)運(yùn)行中. 雖然超立方體網(wǎng)絡(luò)有許多優(yōu)良的性質(zhì)也已取得了很多研究成果[1～ 2]，但它還是有很多缺點(diǎn)，為了改進(jìn)超立方體的缺點(diǎn)，許多專家學(xué)者提出超立方體的某些變形網(wǎng)絡(luò)，例如增廣立方體、k-ary n-立方體等[3～ 4].如今互連網(wǎng)發(fā)展迅速，人們對(duì)網(wǎng)絡(luò)信息傳遞的有效性要求越來(lái)越高，因此某些變形網(wǎng)絡(luò)的性質(zhì)如容錯(cuò)路(圈)和多路等問(wèn)題自然就成了研究熱點(diǎn).變形網(wǎng)絡(luò)中k元n立方體具有直徑小，可遷的,高連通性和高容錯(cuò)性等優(yōu)良性質(zhì).3元n立方體的這些優(yōu)良性質(zhì)使得它在大規(guī)模并行處理系統(tǒng)中具有很強(qiáng)競(jìng)爭(zhēng)力.近幾年來(lái)，學(xué)者對(duì)3元n立方體(容錯(cuò))路的研究已得到了許多的成果[6～8]，本文研究在3元n立方體中的不匹配一對(duì)二不交路覆蓋問(wèn)題得到：

定理1當(dāng)n≥2，邊故障|F|2n-3時(shí)，在中任取3個(gè)頂點(diǎn)x0,y1,y2，則在中有兩條內(nèi)部不交路P1,P2，使得這里P1連接x0和y1，P2連接x0和y2，而且邊故障|F|2n-3為最優(yōu)上界.

1 基本定義

2 定理1證明

對(duì)n作歸納法證明.

給定S=(s1,s2,…,sk)源點(diǎn)集，T=(t1,t2,…,tk)匯點(diǎn)集，若圖G有k條點(diǎn)不交路P1,P2,…,Pk使得

當(dāng)n=2時(shí),顯然定理1成立.對(duì)3k

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

2.1.1 若|F0|=2n-4

連接x0和y2.

2.1.2 若|F0|2n-5

當(dāng)|F1|2n-5時(shí)，由歸納假設(shè)得，在Q[0]-F1中有兩條內(nèi)部不交路l0連接x0和連x0和y2.因不妨設(shè)在中有邊(s0,t0)使得和都無(wú)故障.因?yàn)閨F1|2n-5，由引理1得，在Q[1]-F1中有哈密爾頓路l1連接和在l1中取一條邊(u1,v1)使得和都無(wú)故障，因?yàn)閨F2|2n-5，由引理1得，在Q[2]-F2中有一條哈密爾頓路l2連接和故在中有滿足定理的兩條內(nèi)部不交路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.由歸納假設(shè)得，在Q[0]中有兩條內(nèi)部不交路l0連接x0和連接x0和故在中有滿足定理的兩條內(nèi)部不交路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連接和因?yàn)閨l2|-|F|≥3n-1-(2n-3)>4，故在l2中有一邊(u2,v2)使得且由引理2得，在Q[1]中有兩條內(nèi)部不交路l1連接和連接和y2.故在中有滿足定理的兩條內(nèi)部不交路和

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)使得且由歸納假設(shè)得，在Q[0]中有兩條內(nèi)部不交路l0連接x0和連接x0和因|C2|-|F|≥3n-1-(2n-3)>4，故在C2中有邊(u2,v2)使得且由引理2得，在Q[1]中有兩條內(nèi)部不交路l1連接和y1；l1′連接和y2.故在中有滿足定理的兩條內(nèi)部不交路和

因|F1|2(n-1)-3，由引理1得，在Q[1]-F1中存在一條哈密爾頓路l1連接y1和y2.因|l1|-|F|≥3n-1-(2n-3)>2，故l1中有邊(s1,t1)，使得和都無(wú)故障.由|F2|2(n-1)-3，由引理1得，在Q[2]-F2中有哈密爾頓路l2連接和在l2中取一邊(u2,v2)使得和無(wú)故障且由|F0|2(n-1)-3，由歸納假設(shè)得，在Q[0]-F0中有兩條內(nèi)部不交路l0連接x0和連接x0和故在中有滿足定理的兩條內(nèi)部不交路和

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

不妨設(shè)|F2||F1||F0|2(n-1)-2，由引理1得，在Q[0]-F0中存在一條哈密爾頓圈C0.因|l0|-|F|≥3n-1-(2n-3)>4，故C0有邊(s0,t0)，使得和都無(wú)故障且因|F1|2(n-1)-3，由引理1得，在Q[1]-F1中有哈密爾頓路l1連接y1和因|F2|2(n-1)-3，由引理1得，Q[2]-F2中有哈密爾頓路l2連y2和故中有滿足定理的兩條內(nèi)部不交路和

定理1歸納法證畢.

3 結(jié) 語(yǔ)

定理中的邊故障|F|2n-3是最優(yōu)上界.因?yàn)橹械拿總€(gè)頂點(diǎn)度數(shù)都是2n，當(dāng)與點(diǎn)x0關(guān)聯(lián)的2n-2條邊為故障邊，若剩余兩條與x0關(guān)聯(lián)邊為(x0,y1)和(x0,y2)時(shí)，則中沒(méi)有滿足定理的兩條內(nèi)部不交路P0連接x0和y1；P1連接x0和y2.