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

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

0 引 言

隨著計(jì)算機(jī)系統(tǒng)規(guī)模的擴(kuò)大，系統(tǒng)中出現(xiàn)計(jì)算機(jī)故障或計(jì)算機(jī)間線路故障的可能性隨之增加，因此，網(wǎng)絡(luò)的(容錯(cuò))路問(wèn)題也成了人們關(guān)注的研究點(diǎn).3－ary n 立方體和超立方體網(wǎng)絡(luò)具有結(jié)構(gòu)對(duì)稱，高連通度和最大容錯(cuò)性等優(yōu)良性質(zhì)，因此，它們都是網(wǎng)絡(luò)中非常重要的拓?fù)浣Y(jié)構(gòu).國(guó)內(nèi)外對(duì)3－ary n 立方體和超立方體(容錯(cuò))路的研究已有多年，得到了很多的成果，如:Yang 在文獻(xiàn)［1］中研究了故障點(diǎn)或邊的k－ary n 立方體中圈和路的嵌入問(wèn)題.文獻(xiàn)［2 ～3］研究了線性森林嵌入問(wèn)題.文獻(xiàn)［4 ～5］研究了多條不交路問(wèn)題.本文研究了含有點(diǎn)故障Q3n 中經(jīng)過(guò)指定路的無(wú)故障哈密爾頓圈問(wèn)題.得到如下結(jié)果:

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

本文的圖文術(shù)語(yǔ)和記號(hào)見(jiàn)文獻(xiàn)［6］，一個(gè)圖G的頂點(diǎn)集記為V(G)，邊集記為E(G);以x 和y 為端點(diǎn)的邊記為(x，y).給定子集ε ?E(G)，G 的由ε 導(dǎo)出的子圖記為＜ε ＞;從G 中刪除ε 中所有邊所得到的子圖記為G－ε.k－ary n 立方體簡(jiǎn)稱為，它的每個(gè)節(jié)點(diǎn)T 由一個(gè)n 位k 進(jìn)制字符串(a1，a2，…，an)，0 ≤ai＜k，1 ≤i ≤n，i 稱為節(jié)點(diǎn)T 的第i 維.任意兩點(diǎn)X=(x1，x2，…，xn)與Y=(y1，y2，…，yn)之間有邊，當(dāng)且僅當(dāng)存在一個(gè)整數(shù)j(1≤j ≤n)，使得xj=yj±1(mod k)且xh=yh對(duì)于每個(gè)h ∈{1，2，…，n}－{j}.顯然，當(dāng)k=2是n 正則圖，當(dāng)k ≥3，是2n 正則圖，且的直徑為n×［k/2］(見(jiàn)文獻(xiàn)［6］)，若，而xj=yj，j ∈{1，2，…，n}－{i}，其中1 ≤i ≤n，則稱邊(X，Y)為第i 維邊，中所有第i 維邊的集合記為Ei.顯然，沿第i 維邊可將分成k 個(gè)不交子圖這里是由第i個(gè)比特位xi=j 的所有頂點(diǎn)導(dǎo)出的子圖.

引理1 (見(jiàn)文獻(xiàn)［1］)當(dāng)n ≥2 時(shí)，設(shè)|F|=|Fv|+|Fe|≤2n－3，設(shè)x 和y 是中兩個(gè)頂點(diǎn)，則在中存在一條長(zhǎng)為l 的路P 連接x 和y，這里

2 定理1 證明

當(dāng)h=1 時(shí)，|F0|≤2n－3，由引理1 得，定理1 成立.故只需證當(dāng)2 ≤h ＜n，|F|≤2n－(2h+1)時(shí)，定理1 成立即可.

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

由引理1 得，當(dāng)n=3 時(shí)，則h=2，|F|≤1，設(shè)P=(u0，v0，w0)，令s0與u0相鄰且，由引理1 得，在在－F－u0－v0中存在無(wú)故障哈密爾頓路連接s0與w0，所以定理1 成立.

由h ＜n，則存在j(1 ≤j ≤n)使得|Ej∩P|=0，這里Ej是j 第維的所有邊，沿第j 維將分成三個(gè)不交的，(簡(jiǎn)記為Q［0］，Q［1］，Q［2］)，不失一般性，假設(shè)路P 包含Q［0］中，由于是點(diǎn)可遷，故只需考慮以下三種情況(其他情況討論類似).

情況1:|F0|≤2n－(2h+1)－2.因|F0|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由歸納假設(shè)得，在Q［0］－F0中存在長(zhǎng)為3n－1－|F0|無(wú)故障哈密爾頓圈C 包含路P.因2 ≤h，所以|F1|≤2n－5 或|F2|≤2n－5，由3n－1－|F0|－h(huán)－2|F1|＞0，在Q［0］－F0中存在(w0，s0)∈E(C0－P)使得(w1，s1)無(wú)故障，這里(w1，s1)是(w0，s0)在Q［1］－F1的對(duì)應(yīng)邊，由引理1 得，在Q［1］－F1中有哈密爾頓路P1連接w1和s1.由3n－1－|F1|－2|F2|＞0，在Q［1］－F1中存在(u1，v1)∈E(P1)使得(u2，v2)無(wú)故障，這里(u2，v2)是(u1，v1)在Q［2］－F2的對(duì)應(yīng)邊，由引理1 得，在Q［2］－F2中有哈密爾頓路P2連接u2和v2.則哈密爾頓圈C0∪P1∪P2－(w0，s0)－(u1，v1)+(w0，w1)+(s0，s1)+(u1，u2)+(v1，v2)滿足定理要求.

情況2:|F0|=2n－(2h+1)－1.

不失一般性，設(shè)|F1|=1，|F2=0，t0∈F0，因|F0/t0|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由歸納假設(shè)得，在Q［0］－F0/t0中存在長(zhǎng)為3n－1－|F0/t0|無(wú)故障哈密爾頓圈C0包含路P.不失一般性，設(shè)哈密爾頓圈C0中t0的相鄰頂點(diǎn)為u0，v0，這里u2，v2分別是u0，v0在Q［2］的對(duì)應(yīng)點(diǎn)，由引理1 得，在Q［1］－F1中有哈密爾頓圈C1，取(w1，s1)∈E(C0)使得(w1，s1)在Q［2］的對(duì)應(yīng)邊(w2，s2)且使，由引理2 得，在Q［2］中存在兩條點(diǎn)不交的路和，使得，這里連接w2和連接s2和v2.則哈密爾頓圈s2)+(u0，u2)+(v0，v2)滿足定理要求.

情況3:|F0|=2n－(2h+1).

設(shè)x0，y0∈F0，因|F0/(x0+y0)|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由歸納假設(shè)得，在Q［0］－F0/(x0+y0)中存在無(wú)故障哈密爾頓圈C0包含路P.以下就x0，y0在哈密爾頓圈C0中的位置分三種情況討論

3.1 若C0 =(…u0，x0，v0，…，w0，y0，s0，…)

由引理1 得，在Q［1］中有哈密爾頓路P1連接w1和s1，這里w0，s0在Q［1］的對(duì)應(yīng)點(diǎn)分別為w1，s1，由引理1 得，在Q［2］中有哈密爾頓路P2連接u2和v2.這里u0，v0在Q［2］的對(duì)應(yīng)點(diǎn)分別為u2，v2，則哈密爾頓圈C0∪P1∪P2+(v0，v2)+(w0，w1)+(s0，s1)+(u0，u2)－(u0，x0，v0)－(w0，y0，s0)滿足定理要求.

3.2 若C0 =(…u0，x0，v0，u0，w0，…)

由引理1 得，在Q［1］中有哈密爾頓路P1連接w1和v1，這里w0，v0在Q［1］的對(duì)應(yīng)點(diǎn)分別為w1，v1，由引理1 得，在Q［2］中有哈密爾頓路P2連接u2和v2.這里u0，v2在Q［2］的對(duì)應(yīng)點(diǎn)分別為u2，v2，則哈密爾頓圈C0∪P1∪P2+(w0，w1)+(v0，v1)+(u0，u2)+(v0，v2)－(u0，x0，v0)－(v0，y0，w0)滿足定理要求.

3.3 若C0 =(…u0，x0，y0，v0，…)

由引理1 得，Q［1］在中有哈密爾頓路P1連接u1和v1，這里u0，v0在Q［1］的對(duì)應(yīng)點(diǎn)分別為u1，v1，取(w1，s1)∈E(P1)，由引理1 得，在Q［2］中有哈密爾頓路P2連接w2和s2.這里(w2，s2)是(w1，s1)在Q［2］的對(duì)應(yīng)邊，則哈密爾頓圈C0∪P1∪P2－(u0，x0，y0，v0)+(u0，u1)+(v0，v1)+(w1，w2)+(s1，s2)滿足定理要求.

說(shuō)明:若|F|=2n－(2h+1)+2，當(dāng)h=1 時(shí)，即|F|=2n－1，顯然結(jié)論不成立.若|F|=2n－(2h+1)+1，假設(shè)h=1 時(shí)，當(dāng)n=2 時(shí)，易證結(jié)論成立.當(dāng)n ≥3 時(shí)，結(jié)論是否成立仍有待研究.

［1］ Yang M.C.，Tan J.M.，Hsu L.H.Hamiltonian Circuit and Linear Array Embeddings in Faulty k－ary n－cubes［J］.Journal of Parallel and Distributed Computing，2007，(4):362－368.

［2］ Yuxing Yang，Shiying Wang.Fault－free Hamiltonian Cycles Passing Through a Linear Forest in Ternary n－cubes with Faulty Edges［J］.Theoretical Computer Science，2013，491:78－82.

［3］ Shiying Wang，Yuxing Yang，Jing Li，Shangwei Lin.Hamiltonian Cycles Passing Through Linear Forests in k－ary n－cubes［J］.Discrete Applied Mathematics，2011，159:1425–1435.

［4］ 佘衛(wèi)強(qiáng).點(diǎn)故障3－ary n 立方體中兩條無(wú)故障 點(diǎn)不交路［J］.佳木斯大學(xué)學(xué)報(bào)，2013，(11):829－932.

［5］ Shurong Zhang，Shiying Wang.Hamiltonian Cycles Passing Through Linear Forests in k－ary n－cubes［J］.Discrete Applied Mathematics，2011，159:1425–1435.

［6］ Bondy J.A.，Murty U.S.R.Graph Theory with Applications，Macmillan Press，London，1976.