含故障邊的k元4立方體中的哈密爾頓性

田小潤，李 晶，張建秀

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

二十世紀(jì)電子計算機的出現(xiàn)，引發(fā)了信息科學(xué)突飛猛進(jìn)的發(fā)展。近年來信息量的不斷增加，在太空、國防、科技等各個領(lǐng)域中，迫切地要求計算機儲存能力和運算速度的提升。因此，大規(guī)模并行計算機系統(tǒng)應(yīng)用而生。大規(guī)模并行計算機系統(tǒng)中，互連網(wǎng)絡(luò)在硬件成本、通信性能力、高效算法的潛力和容錯能力方面起著至關(guān)重要的作用。近幾十年來，有相當(dāng)多的互連網(wǎng)絡(luò)被提出作為大規(guī)模多處理器系統(tǒng)的底層拓?fù)洹Ｗ盍餍谢ミB網(wǎng)絡(luò)之一是k元n立方體網(wǎng)絡(luò)。k元n立方體網(wǎng)絡(luò)具有許多理想的特性，比如易于實現(xiàn)、低延遲和高帶寬的處理器間通信。因此，許多分布內(nèi)存并行系統(tǒng)都是用k元n立方體網(wǎng)絡(luò)構(gòu)建的，形成底層拓?fù)浣Y(jié)構(gòu)，如IBMBlueGene[1]、J-machine[2]和CrayT3D[3].

1 預(yù)備知識

一個拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò)用圖G=(V(G)，E(G))來表示，其中V(G)代表圖的頂點集，E(G)代表圖的邊集。經(jīng)過圖G中每個頂點僅一次的路(圈)，稱為圖G的哈密爾頓路(圈)，記為H路。若路的兩個端點為s和t，則這條路可表示為(s，t)-路。如果一個圖有哈密爾頓圈，則該圖是哈密爾頓的。如果存在一條哈密爾頓路連接圖中任意兩個不同的頂點，則稱圖G是哈密爾頓連通的。二部圖是指一個圖G，它的頂點集可以分解為兩個(非空)子集X和Y，使得每條邊都有一個端點在X中，另一個端點在Y中。若點x在X中，點y在Y中，則稱x、y在不同部。

圖1 劃分為Q[0]，Q[1]，…Q[k-1]Fig.1 The division of Q[0]，Q[1]，…Q[k-1]

下面給出證明中需要用到的引理：

2 主要結(jié)論的證明

引理3在Q[i:j]中，設(shè)|F[i:j]|≤13，|Fp|≤7，且δ(Q[p]-Fp)≥2，其中p=i，i+1，…，j，則對Q[i:j]中任意兩個不同部點s和t，當(dāng)s，t∈Q[i]∪Q[j]時，Q[i:j]-F[i:j]中有(s，t)-H路。

證明：因為s，t∈Q[i]∪Q[j]，根據(jù)對稱性，下面分兩種情形討論。

情形1s，t∈Q[i]

斷言：路P上至少有一條可擴邊可擴到Q[i+1].

因為|F[i:j]|≤13，最多有13條故障d維邊。由于路P中包含k3-1條候選邊，而每條故障d維邊最多會使兩條邊不可擴。當(dāng)k≥4時，k3-1?2×13≥2×|F[i:j]|，所以斷言成立。

設(shè)邊(xi，yi)可擴到Q[i+1]，(xi+1，yi+1)是(xi，yi)在Q[i+1]上的對應(yīng)邊。由引理1，Q[i+1]-Fi+1中有(xi+1，yi+1)-H路P1.用路〈xi，xi+1，P1，yi+1，yi〉替換路P上的邊(xi，yi)，可得到Q[i:i+1]上的(s，t)-H路。此時，在新哈密爾頓路上可找到可擴邊，依此類推，最終得到Q[i:j]上的(s，t)-H路，如圖2所示。

圖 2 引理3 情形1Fig.2 Case 1 of lemma 3

情形2s∈Q[i]，t∈Q[j]

圖3 引理3 情形2Fig.3 Case 2 of lemma 3

證畢。

引理4在Q[i:j]中，設(shè)S={s1，s2}、T={t1，t2}為不同部的頂點集。若|F|≤3，|F∩Ed|≤4，且S∪T?Q[i]∪Q[j]，則Q[i:j]有指定2-DPC.

證明：用數(shù)學(xué)歸納法證明。

當(dāng)i=j，即Q[i:j]中只有1個子立方體時，根據(jù)引理2，結(jié)論成立。

假設(shè)Q[i:j]中有k-1(k≥2)個子立方體時，結(jié)論成立。

下面證明Q[i:j]中有k個子立方體時結(jié)論也成立。

情形1S∪T?Q[i]或S∪T?Q[j]

因為S∪T?Q[i]∪Q[j]，根據(jù)對稱性，只證明S∪T?Q[i]的情形。

圖4 引理4 情形1Fig.4 Case 1 of lemma 4

情形2{s1，s2，t1}?Q[i]，{t2}?Q[j]

如圖5，在Q[i]中取一個與t1在同一部的可擴點xi，且xi可擴到Q[i+1]，設(shè)xi+1是xi在Q[i+1]中的對應(yīng)點，顯然xi+1與t2不在同一部。由引理2知，Q[i]-Fi中存在{P1，P3}是一個指定2-DPC，其中P1連接s1和t1，P2連接s2和xi.由引理3知，Q[i+1:j]-Fi+1:j中存在(xi+1，t2)-H路P3.令P4=〈s2，P2，xi，xi+1，P3，t2〉.此時{P1，P4}是Q[i:j]的一個指定2-DPC.因此結(jié)論成立。

圖5 引理4 情形2Fig.5 Case 2 of lemma 4

情形3{s1，s2，}?Q[i]，{t1，t2}?Q[j]

圖6 引理4 情形3Fig.6 Case 3 of lemma 4

情形4{s1，t1，}?Q[i]，{s2，t2}?Q[j]

由引理1和引理3，在Q[i]中構(gòu)造(s1，t1)-H路P1，Q[i+1:j]中構(gòu)造(s2，t2)-H路P2即可。

情形5{s1，t2，}?Q[i]，{s2，t1}?Q[j]

此時，變換s2與t2的位置，則情況同情形3.證畢。

證明由引理1可知，當(dāng)|F|≤11時，結(jié)論成立。故本文只需討論|F|∈{12，13}時的情形。

情形1δ(Q[i]-Fi)≥2，i=0，1，2，…，k-1

不失一般性，設(shè)|F0|=max{|Fi|，i=0，1，2，…，k-1}，則|F0|≤9.

圖7 定理1 情形1Fig.7 Case 1 of theorem 1

情形2子立方體中存在1度點

情形2.1Q[i]中僅有1個1度點

設(shè)該1度點為u，且u∈Q[0]，此時|F0|≥5且|F0∪F1∪…Fk-1|≤9.

圖8 定理1 情形2.1Fig.8 Case 2.1 of theorem 1

圖9 定理1 情形2.1Fig.9 Case 2.1 of theorem 1

情形2.2Q[i]中存在2個1度點

設(shè)兩個1度點分別用u、v來表示。此時點u、v必在同一個子立方中。如若點u∈Q[i]、v∈Q[j]中，情形如圖10所示。因為點u、v均為1度點，沿維d劃分后，子立方體與點u、v相鄰的故障邊數(shù)分別至少為5，即|Fi∪Fj|≥10，與|F1∪F2∪…Fk-1|≤9矛盾。故點u、v在同一子立方中，且為鄰點。

圖10 定理1 情形2.2Fig.10 Case 2.2 of theorem 1

不失一般性，假設(shè)u∈Q[0]且v∈Q[0]，如圖11所示，|F0|=9.取u的一個可擴鄰點w使得(u，w)∈F0.令F′0=F0{(u，v)，(u，w)}，則|F′0|=7，此時，證明同情形 2.1中的|F0|=9情形一樣。

圖11 定理1 情形2.2Fig.11 Case 2.2 of theorem 1

情形2.3Q[i]中存在3個1度點

設(shè)該3個1度點為u、v、w.由已知條件可知，|F|≤13，所以這3個1度點當(dāng)且僅當(dāng)有一種排列方式，如圖12示。故在Q[i]中，3個1度點都在同一個子立方中。假設(shè)u∈Q[0]、v∈Q[0]且w∈Q[0]，此時|F0|>9，與|Fi|≤9矛盾。因此此種情形不存在。

圖12 定理1 情形2.3Fig.12 Case 2.3 of theorem 1

證畢。

3 結(jié)論