點故障3－ary n 立方體中經(jīng)過指定路的無故障哈密爾頓圈①

佘衛(wèi)強

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

0 引 言

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

1 預備知識

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

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

2 定理1 證明

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

對n 作歸納法證明.

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

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

情況1:|F0|≤2n－(2h+1)－2.因|F0|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由歸納假設(shè)得，在Q［0］－F0中存在長為3n－1－|F0|無故障哈密爾頓圈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)無故障，這里(w1，s1)是(w0，s0)在Q［1］－F1的對應(yīng)邊，由引理1 得，在Q［1］－F1中有哈密爾頓路P1連接w1和s1.由3n－1－|F1|－2|F2|＞0，在Q［1］－F1中存在(u1，v1)∈E(P1)使得(u2，v2)無故障，這里(u2，v2)是(u1，v1)在Q［2］－F2的對應(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中存在長為3n－1－|F0/t0|無故障哈密爾頓圈C0包含路P.不失一般性，設(shè)哈密爾頓圈C0中t0的相鄰頂點為u0，v0，這里u2，v2分別是u0，v0在Q［2］的對應(yīng)點，由引理1 得，在Q［1］－F1中有哈密爾頓圈C1，取(w1，s1)∈E(C0)使得(w1，s1)在Q［2］的對應(yīng)邊(w2，s2)且使，由引理2 得，在Q［2］中存在兩條點不交的路和，使得，這里連接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)中存在無故障哈密爾頓圈C0包含路P.以下就x0，y0在哈密爾頓圈C0中的位置分三種情況討論

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

由引理1 得，在Q［1］中有哈密爾頓路P1連接w1和s1，這里w0，s0在Q［1］的對應(yīng)點分別為w1，s1，由引理1 得，在Q［2］中有哈密爾頓路P2連接u2和v2.這里u0，v0在Q［2］的對應(yīng)點分別為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］的對應(yīng)點分別為w1，v1，由引理1 得，在Q［2］中有哈密爾頓路P2連接u2和v2.這里u0，v2在Q［2］的對應(yīng)點分別為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］的對應(yīng)點分別為u1，v1，取(w1，s1)∈E(P1)，由引理1 得，在Q［2］中有哈密爾頓路P2連接w2和s2.這里(w2，s2)是(w1，s1)在Q［2］的對應(yīng)邊，則哈密爾頓圈C0∪P1∪P2－(u0，x0，y0，v0)+(u0，u1)+(v0，v1)+(w1，w2)+(s1，s2)滿足定理要求.

說明:若|F|=2n－(2h+1)+2，當h=1 時，即|F|=2n－1，顯然結(jié)論不成立.若|F|=2n－(2h+1)+1，假設(shè)h=1 時，當n=2 時，易證結(jié)論成立.當n ≥3 時，結(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)強.點故障3－ary n 立方體中兩條無故障 點不交路［J］.佳木斯大學學報，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.