二維環(huán)面網(wǎng)絡(luò)的邊容錯(cuò)哈密爾頓性

高曉慧，李 晶，謝秀梅

(1.太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024；2.大同市廣靈一中，山西 大同 037500)

1 背景介紹

直連網(wǎng)絡(luò)是一種常見(jiàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，已經(jīng)廣泛應(yīng)用于多處理器系統(tǒng)，多計(jì)算機(jī)系統(tǒng)以及集群系統(tǒng)中。隨著并行計(jì)算機(jī)互連網(wǎng)絡(luò)和VLSI技術(shù)的迅速發(fā)展，系統(tǒng)中的并行處理機(jī)越來(lái)越多，仍采用傳統(tǒng)的網(wǎng)絡(luò)互連結(jié)構(gòu)已不能滿足需求。于是人們對(duì)并行計(jì)算機(jī)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了大量的研究[1-4]，并對(duì)其中的一些拓?fù)浣Y(jié)構(gòu)已研制出了相應(yīng)的商用和研究用的并行計(jì)算機(jī)系統(tǒng)。網(wǎng)絡(luò)是一種完全對(duì)稱(chēng)的直連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，它具有很多優(yōu)秀的網(wǎng)絡(luò)特性[5]，如規(guī)則對(duì)稱(chēng)性，路徑多樣性以及良好的擴(kuò)展性。因此它廣泛應(yīng)用于許多商用系統(tǒng)中，例如，2004年底評(píng)出的全球超級(jí)計(jì)算機(jī)TOP100中排名首位的IBM BlueGene/L就采用網(wǎng)絡(luò)；而另一家通信設(shè)備制造商，Avici公司在其推出的世界上第一臺(tái)太比特路由器中也采用網(wǎng)絡(luò)作為其交換網(wǎng)絡(luò)拓?fù)洹?/p>

圖嵌入是將一個(gè)客圖映射到一個(gè)主圖中的一項(xiàng)技術(shù)，是評(píng)價(jià)一個(gè)網(wǎng)絡(luò)性能的重要指標(biāo)。 因此，對(duì)采用結(jié)構(gòu)的多處理器系統(tǒng)進(jìn)行嵌入研究是非常必要的。許多應(yīng)用如結(jié)構(gòu)仿真和處理器分配都可以用圖嵌入來(lái)建模。在并行處理系統(tǒng)中，由于路和圈的結(jié)構(gòu)均被用于模擬線性數(shù)組，所以在圖嵌入問(wèn)題中經(jīng)常會(huì)選擇路和圈來(lái)作為客圖[6]。圖的容錯(cuò)性是指當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，該網(wǎng)絡(luò)仍然具有的一些好的性質(zhì)。二維網(wǎng)絡(luò)是二維網(wǎng)絡(luò)的擴(kuò)展，它比網(wǎng)絡(luò)具有更好的性能，近十幾年來(lái)人們對(duì)網(wǎng)絡(luò)的容錯(cuò)嵌入進(jìn)行了大量的研究。Jung-Heum Park等人[7]證明了故障邊數(shù)為1時(shí)，Torus(m,n)是哈密爾頓的，其中m≥2，偶數(shù)n≥4.Hee-Chul Kim等人[8]證明了故障元素的個(gè)數(shù)為2時(shí)，Torus(m,n)是哈密爾頓的，其中m,n≥3，且n是奇數(shù)。Yonghong Xiang等人[9]證明了故障邊數(shù)為3時(shí)，Torus(m,n)是哈密爾頓的，其中m,n≥3且每個(gè)頂點(diǎn)至少有2度。本文主要研究故障邊數(shù)達(dá)到4，在一類(lèi)條件假設(shè)下，二維網(wǎng)絡(luò)的哈密爾頓圈嵌入問(wèn)題。具體來(lái)講，證明了在假設(shè)條件下，二維(偶數(shù))在具有至多4條故障邊時(shí)仍包含哈密爾頓圈。

(1)每個(gè)頂點(diǎn)的度至少是2；

(2)不存在具有兩個(gè)度為2的不相鄰的頂點(diǎn)的4圈。

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

一個(gè)二維m×n的環(huán)面(記作Torus(m,n)，其中m,n≥3)是由mn個(gè)頂點(diǎn)構(gòu)成，且每個(gè)頂點(diǎn)用vi,j來(lái)表示，其中1≤i≤m，1≤j≤n.兩個(gè)頂點(diǎn)vi,j與vi′,j′相鄰當(dāng)且僅當(dāng)i′=i，j′=j±1(模n)或j′=j,i′=1±1(模m).對(duì)于每個(gè)i，邊(vi,1,vi,n)稱(chēng)為行環(huán)繞邊；對(duì)于每個(gè)j，邊(vi,j,vm,j)稱(chēng)為列環(huán)繞邊。圖1(a)為T(mén)orus(3,4).注意到Torus(m,n)是一個(gè)4正則圖(每個(gè)頂點(diǎn)的度為4)，且連通度κ(G)=4.將Torus(m,n)的所有列環(huán)繞邊刪去所生成的圖記作Row-Torus(m,n).圖1(b)為Row-Torus(3,4)，它是一個(gè)3連通的偶圖。

圖1 Torus(3,4)和Row-Torus(3,4)Fig.1 Torus(3,4) and Row-Torus(3,4)

設(shè)G是Torus(m,n)或Row-Torus(m,n).E(G)代表G的邊集。Row(a∶b)是由{vi,j∶a≤i≤b,1≤j≤n}生成的G的子圖；Col(a∶b)是由{vi,j∶ 1≤i≤m,a≤j≤b}生成的G的子圖。Row(a∶a)和col(a∶a)可以分別用Row(a)和Col(a)來(lái)表示。為方便，稱(chēng)所有Row(a)上的邊為行邊，所有Col(a)上的邊為列邊。設(shè)(vi,j,vi,j+1)為Row(i)上一條行邊，其中1≤i≤m.若與這條行邊相鄰的兩條列邊(vi,j,vr,j)與(vi,j+1,vr,j+1)同時(shí)非故障，其中r=i-1或r=i+1，則稱(chēng)這條邊是r-行擴(kuò)展邊。列擴(kuò)展邊類(lèi)似定義。

當(dāng)m和n都是偶數(shù)時(shí)，Torus(m,n)是偶圖；如果n是偶數(shù)，Row-Torus(m,n)也是偶圖。對(duì)偶圖G中的一個(gè)頂點(diǎn)vi,j，若i+j是偶數(shù)，則稱(chēng)它是偶頂點(diǎn)，否則是奇頂點(diǎn)。一條路P=〈v0,v1,…,vt〉是使得任意兩個(gè)連續(xù)的頂點(diǎn)都相鄰的一條互不相同的頂點(diǎn)序列。經(jīng)過(guò)圖G所有頂點(diǎn)恰一次的路是Hamilton路。在一個(gè)偶圖G中，若不同部中的任意兩個(gè)頂點(diǎn)s與t，均存在一條從s到t的Hamilton路，則G是Hamiltonian-Laceable[10]。經(jīng)過(guò)G的每個(gè)頂點(diǎn)恰一次的圈被稱(chēng)為圖G的Hamilton圈。稱(chēng)一個(gè)包含Hamilton圈的圖是Hamilton圖。

大量的文獻(xiàn)研究了Torus(m,n)和Row-Torus(m,n)的拓?fù)湫再|(zhì)，得到了許多好的研究結(jié)果。本文中用到了以下的結(jié)論：

引理1[7]：設(shè)F是Row-Torus(m,n)的一個(gè)故障邊集，其中m≥2，偶數(shù)n≥4.若|F|≤1，則Row-Torus(m,n)-F是Hamiltonian-laceable.

由上述定理，有下面的結(jié)論：

推論1：設(shè)F是Row-Torus(m,n)的一個(gè)故障邊集，其中m≥2，偶數(shù)n≥4.若|F|≤1，則Row-Torus(m,n)-F是Hamiltonian.

引理2[7]：設(shè)F是Row-Torus(m,n)的一個(gè)故障邊集，其中m≥3，偶數(shù)n≥6.若|F|=2且這2條故障邊不同時(shí)與一個(gè)3度頂點(diǎn)關(guān)聯(lián)，則Row-Torus(m,n)-F是Hamiltonian.

3 主要結(jié)果的證明

這一部分將證明：在滿足條件(1)與(2)的前提下，Torus(k,k)是4邊容錯(cuò)的Hamilton圖，其中偶數(shù)k≥6.

令F是Torus(k,k)的故障邊集，且|F|≤4.為了方便，用Fr(Fc)表示所有故障行(列)邊集合。不妨設(shè)|Fr|≥|Fc|，則|Fr|≥2.對(duì)于每個(gè)j∈{1,2,…,k}，記Cj=Col(j)，記Ej,j+1為Cj與Cj+1之間的行邊集合，即Ej,j+1={(vi,j,vi,j+1)|i∈{1,2,…,k}}，其中j+1模k.

定理1：如果存在一個(gè)j′∈{1,2,…,k}，使得|Ej′,j′+1∩F|≥2，那么Torus(k,k)-F是Hamiltonian.

證明：由于|Ej′,j′+1∩F|≥2且|F|≤4，所以Torus(k,k)-Ej′,j′+1中至多有2條故障邊。注意到Torus(k,k)-Ej′,j′+1與Row-Torus(k,k)同構(gòu)。如果Torus(k,k)-Ej′,j′+1至多有1條故障邊，或者有2條故障邊但不同時(shí)與一個(gè)3度頂點(diǎn)關(guān)聯(lián)，則分別由推論1與引理2知Torus(k,k)-Ej′,j′+1-F中存在Hamilton圈，故Torus(k,k)-F是Hamiltonian.

情況1另1條故障邊是(vi,j′-1,vi,j′).

由于條件(1)成立且Torus(k,k)-Ej′,j′+1中至多有2條故障邊，所以邊(vi,j′,vi,j′+1)與邊(vp,j′-1,vp,j′)非故障。又Torus(k,k)-Cj′與Row-Torus(k-1,k)是同構(gòu)的，由引理1得，Torus(k,k)-Cj′中存在一條從vp,j′-1到vi,j′+1的Hamilton路P0.令P1=Cj′-(vi,j′,vp,j′).連接P0與P1，如圖2(a)所示，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

下面考慮對(duì)于任意的j∈{1,2,…,k}，當(dāng)|Ej,j+1∩F|≤1時(shí)，Torus(k,k)-F仍然是Hamiltonian.首先討論一種特殊的情況：

定理2：如果存在一個(gè)j′∈{1,2,…,k}，使得Cj′中存在1條故障邊與2條故障行邊相鄰，那么Torus(k,k)-F是Hamiltonian.

證明：令e0=(vp,j′,vp+1,j′)是Cj′中滿足上面條件的故障邊，其中p∈{1,2,…,k}，則與e0相鄰的2條故障行邊的集合是W0={(vp,j′-1,vp,j′),(vp+1,j′,vp+1,j′+1)}或者是W1={(vp,j′,vp,j′+1),(vp+1,j′-1,vp+1,j′)}，不妨設(shè)前者成立。那么W1中的2條邊均非故障。由于|Fr|≥2，所以Cj′中至多有2條故障列邊。

如果Cj′中僅有1條故障邊e0，令P0=Cj′-e0.注意到Torus(k,k)-Cj′與Row-Torus(k-1,k)同構(gòu)，由引理1得，Torus(k,k)-Cj′-F中存在一條從vp+1,j′-1到vp,j′+1的Hamilton路P1.連接P0與P1，如圖3(a)所示，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

如果Cj′中有2條故障邊e0，e1，則e1一定不與e0相鄰?？紤]Torus(k,k)中Row(p-1∶p+1)與Row(p+2∶p-2)兩部分。注意到Row(p-1∶p+1)與Row-Torus(3,k)同構(gòu)，且至多有3條故障邊。令F′={(vp,j′-1,vp,j′),(vp,j′,vp+1,j′)}，由引理2得，Row(p-1∶p+1)-F′中存在經(jīng)過(guò)邊(vp+1,j′,vp+1,j′+1)的Hamilton圈C0，令P2=C0-(vp+1,j′,vp+1,j′+1)，又Row(p+2∶p-2)與Row-Torus(k-3,k)同構(gòu)，由引理得，Row(p+2∶p-2)-F中有一條從vp+2,j′到vp+2,j′+1的Hamilton路P3.連接P2與P3，如圖3(b)所示，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

定理3：如果存在一個(gè)j′∈{1,2,…,k}，使得Cj′中有且僅有2條故障邊，那么Torus(k,k)-F是Hamiltonian.

證明：令邊(vp,j′,vp+1,j′)與(vq,j′,vq+1,j′)是Cj′中的2條故障列邊，其中p,q∈{1,2,…,k}，p≠q，則另2條故障邊為行邊。需考慮Cj′中的任意1條故障邊至多與1條故障行邊相鄰，則W0={(vp,j′,vp,j′+1),(vp+1,j′,vp+1,j′+1),(vq,j′,vq,j′-1),(vq+1,j′,vq+1,j′-1)}或W1={(vp,j′,vp,j′-1),(vp+1,j′,vp+1,j′-1),(vq,j′,vq,j′+1),(vq+1,j′,vq+1,j′+1)}是非故障邊集，不妨設(shè)W0是非故障邊集。令P0=Cj′-(vp,j′,vp+1,j′)-(vq,j′,vq+1,j′).

選擇一個(gè)整數(shù)p*如下：如果(Ej′,j′+1∪Ej′-1,j′)∩F≠φ，令P*=j′+1；否則令P*是沿j′+1,j′+2,…,k,1,2,…,j′-2的順序，第一個(gè)滿足Ep*,p*+1∩F≠φ的整數(shù)。由定理1，設(shè)|Ep*,p*+1∩F|=1.由P*的選取知，Torus(k,k)-Cj′-Ep*+1,p*+2中Col(j′+1∶p*+1)與Col(p*+2∶j′-1)都至多包含1條故障邊。注意到Col(j′+1∶p*+1)與Row-Torus(|p-j′|+1∶k)同構(gòu)且|p-j′|+1≥2，由引理1知，Col(j′+1∶p*+1)-F中存在一條從vp,j′+1到vp+1,j′+1的Hamilton路P1.當(dāng)Col(p*+2∶j′-1)僅有1列，即p*+2=j′-1時(shí)，Cj′-1-(vq,j′-1,vq+1,j′-1)是一條從點(diǎn)vq,j′-1到vq+1,j′-1的Hamilton路P2.當(dāng)Col(p*+2∶j′-1)至少有2列時(shí)，同理Col(p*+2,j′-1)-F中存在一條從點(diǎn)vq,j′-1到點(diǎn)vq+1,j′-1的Hamilton路P2.連接P0，P1和P2，如圖4所示，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

定理4：如果存在一個(gè)j′∈{1,2,…,k}，使得Cj′中存在1條故障的非(j′-1)-列擴(kuò)展邊，Cj′+1中存在1條故障的非(j′+2)-列擴(kuò)展邊，那么Torus(k,k)-F是Hamiltonian.

證明：不妨設(shè)e0=(v1,j′,v2,j′)是Cj′中1條故障的非(j′-1)-列擴(kuò)展邊，e1=(vp,j′+1,vp+1,j′+1)是Cj′+1中1條故障的非(j′+2)-列擴(kuò)展邊，其中1≤p≤k/2.顯然邊(v1,j′-1,v1,j′)與(v2,j′-1,v2,j′)中僅有1條故障邊，邊(vp,j′+1,vp,j′+2)與(vp+1,j′+1,vp+1,j′+2)中也僅有1條故障邊.注意到Torus(k,k)-Cj′-Cj′+1與Row-Torus(k-2,k)同構(gòu)，由引理1知，Torus(k,k)-Cj′-Cj′+1是Hamiltonian-laceable.

如果p=1，令P0=Cj′-e0，P1=Cj′+1-e1，連接P0與P1得到Col(j′∶j′+1)-F的Hamilton圈C0.由|Ej′,j′+1∩F|≤1且k≥6，則Cj′中存在一條(j′-1)-列擴(kuò)展邊(vq,j′,vq+1,j′)，其中q∈{2,3,…,k}.令P2=C0-(vq,j′,vq+1,j′).顯然，Torus(k,k)-Cj′-Cj′+1中存在一條從vq,j′-1到vq+1,j′-1的Hamilton路P3.連接P2與P3，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

圖3 定理2的示意圖Fig.3 An illustration for Theorem 2

圖4 定理3的示意圖Fig.4 An illustration for Theorem 3

下設(shè)p≠1，根據(jù)2條故障行邊的位置，對(duì)以下3種情況進(jìn)行討論：

情況1(vp+1,j′+1,vp+1,j′+2)或(v1,j′-1,v1,j′)是故障邊。

由對(duì)稱(chēng)性，不妨設(shè)(vp+1,j′+1,vp+1,j′+2)是故障邊，則邊(vp,j′+1,vp,j′+2)非故障。由于2≤p≤k/2且偶數(shù)k≥6，則p+2≤k/2+2且vp+2,j′≠v1,j′.那么(vp+2,j′-1,vp+2,j′)是非故障邊。Torus(k,k)-Cj′-Cj′+1中存在一條從vp,j′+2到vp+2,j′-1的Hamilton路P4.如圖5(a)所示，在Col(j′∶j′+1)-F中找到一條從vp+2,j′到vp,j′+1的Hamilton路P5，連接P4和P5，構(gòu)造了Torus(k,k)-F的一個(gè)Hamilton圈。

情況2(vp,j′+1,vp,j′+2)與(v2,j′-1,v2,j′)是故障邊。

當(dāng)p=2時(shí)，全部故障邊都確定，如圖5(b)所示，邊(v1,j′-1,v1,j′)與(v3,j′+1,v3,j′+2)是非故障的。Torus(k,k)-Cj′-Cj′+1中存在一條從v1,j′-1到v3,j′+2的Hamilton路P4.令P5=Cj′-e0，P6=Cj′+1-e1.那么〈v1,j′-1,v1,j′,P5,v2,j′,v2,j′+1,P6，v3,j′+1,v3,j′+2,P4,v1,j′-1〉為T(mén)orus(k,k)-F的一個(gè)Hamilton圈。

由條件(2)知，p≠3.當(dāng)p≥4時(shí)，(v1,j′-1,v1,j′)與(v3,j′+1,v3,j′+2)均是非故障邊。Torus(k,k)-Cj′-Cj′+1中存在一條從v1,j′-1到v3,j′+2的Hamilton路P4.注意到Cj′-e0-(vp,j′,vp+1,j′)是由從點(diǎn)v1,j′到點(diǎn)vp+1,j′的路P7與從點(diǎn)v2,j′到點(diǎn)vp,j′的路P8組成；Cj′+1-e1-(v2,j′+1,v3,j′+1)是由從點(diǎn)vp+1,j′+1到點(diǎn)v2,j′+1的路P6與從點(diǎn)vp,j′+1到點(diǎn)v3,j′+1的路P10組成。如圖5(c)所示，構(gòu)造Torus(k,k)-F的一個(gè)Hamilton圈：〈v1,j′-1,v1,j′,P7,vp+1,j′,vp+1,j′+1,P9,v2,j′+1,v2,j′,P8，vp,j′,vp,j′+1,P10,v3,j′+1,v3,j′+2,P4,v1,j′-1〉.

定理5：設(shè)F是Torus(k,k)的一個(gè)故障邊集且|F|≤4，其中偶數(shù)k≥6，若條件(1)與條件(2)滿足，則Torus(k,k)-F是Hamiltonian.

證明：只需證明|F|=4的情形即可，不失一般性設(shè)|Fr|≥|Fc|，則|Fr|≥2.由定理1，只需考慮|Ej,j+1∩F|≤1，其中1≤j≤k.令e0=(v1,1,v1,k)是Fr中的1條故障行邊，另1條故障邊為e1=(vi′,j′,vi′,j′+1)，其中i′∈{1,2,…,k}，j′∈{1,2,…,k-1}.Torus(k,k)-Ek,1-Ej′,j′+1中有2條故障邊。注意Torus(k,k)-Ek,1-Ej′,j′+1中Col(1∶j′)與Row-Torus(j′∶k)同構(gòu)；Col(j′+1∶k)與Row-Torus(k-j′∶k)同構(gòu)。下面討論兩種情況：

情況1Col(1∶j′)與Col(j′+1∶k)中各有1條故障邊。

首先假設(shè)Col(1∶j′)與Col(j′+1∶k)都至少包含2列。顯然Cj′中存在一條(j′+1)-列擴(kuò)展邊(vp,j′,vp+1,j′)，其中p∈{1,2,…,k}.由引理1知，Col(1∶j′)-F中存在一條從vp,j′到vp+1,j′的Hamilton路P0；Col(j′+1∶k)中存在一條從vp,j′+1到vp+1,j′+1的Hamilton路P1.連接P0與P1，得到Torus(k,k)-F的一個(gè)Hamilton圈。

其次假設(shè)Col(1∶j′)與Col(j′+1∶k)中的一個(gè)僅包含1列，不失一般性設(shè)Col(1∶j′)僅包含1列，即j′=1且Col(1∶j′)=C1.令Col(1∶j′)中的故障邊e2=(vq,1,vq+1,1)，其中q∈{1,2,…,k}.如果e2同時(shí)與2條故障行邊e0，e1相鄰，由定理2知結(jié)論成立。如果e2至多與{e0,e1}中的1條故障邊相鄰，則e2是2-列擴(kuò)展邊或是k-列擴(kuò)展邊，不妨設(shè)e2是2-列擴(kuò)展邊。令P2[vq,1,vq+1,1]=C1-(vq,1,vq+1,1).由引理1知，Col(2∶k)-F中存在一條從vq,2到vq+1,2的Hamilton路P3.連接P2與P3，得到Torus(k,k)-F中的一個(gè)Hamilton圈。

圖5 定理4的情況1與情況2Fig.5 Cases of Theorem 4.(a) Case 1;(b)and(c) Case 2

情況2Col(1∶j′)與Col(j′+1∶k)中，有一個(gè)包含2條故障邊。

不失一般性，設(shè)Col(1∶j′)中有2條故障邊，Col(j′+1∶k)中無(wú)故障。如果Col(1∶j′)僅有1列，這種情況在定理3中討論過(guò)。下面設(shè)Col(1∶j′)中至少包含2列：

情況2.1Col(1∶j′)中至少包含3列。

若Col(1∶j′)中的2條故障邊不同時(shí)與一個(gè)3度頂點(diǎn)關(guān)聯(lián)，由引理2知，Col(1∶j′)-F中存在一條Hamilton圈C.注意到C至少經(jīng)過(guò)Cj′中的3條邊，則選擇C∩Cj′中的一條(j′+1)-列擴(kuò)展邊(vp,j′,vp+1,j′)，其中p∈{1,2,…,k}.令P0=C-(vp,j′,vp+1,j′).顯然Col(j′+1∶k)中存在一條連接vp,j′+1與vp+1,j′+1的Hamilton路P1.將P0與P1連接，構(gòu)造了Torus(k,k)-F的一個(gè)Hamilton圈。

如果Col(1∶j′)中的2條故障邊同時(shí)與一個(gè)3度頂點(diǎn)關(guān)聯(lián)，不妨設(shè)它是點(diǎn)vq,j′，其中q∈{1,2,…,k}.由定理2與定理3，只需考慮Cj′中僅有1條故障邊，且這條故障邊不與e1相鄰的情況，設(shè)Cj′中的故障邊為(vq,j′,vq+1,j′)，顯然(vq,j′,vq+1,j′)是(j′+1)-列擴(kuò)展邊。令F′=F∩E(Col(1∶j′))-(vq,j′,vq+1,j′)，則|F′|=1.由引理1知，Col(1∶j′)-F′中存在一條從vq,j′到vq+1,j′的Hamilton路P2.又Col(j′+1∶k)中存在一條連接vq,j′+1與vq+1,j′+1的Hamilton路P3.連接P2與P3，構(gòu)造Torus(k,k)-F的一個(gè)Hamilton圈。

情況2.2Col(1∶j′)僅包含2列，即j′=2.

顯然，Col(1∶ 2)中至少有1條故障列邊。如果C1中存在1條故障的k-列擴(kuò)展邊，或者C2中存在1條故障的3-列擴(kuò)展邊，則構(gòu)造Hamilton圈的方法如情況2.1第二自然段。

如果Col(1∶ 2)中的2條故障邊都是列邊，由定理3與4知結(jié)論成立。下面考慮1條故障邊是行邊(即E1,2中的邊)的情況。不失一般性，設(shè)Col(1∶ 2)中的故障列邊在C2中。Torus(k,k)中的4條故障邊為：e0=(v1,1,v1,k)，e1∈E2,3，e2∈E1,2，e3∈E(C2).重新劃分Torus(k,k)，即Torus(k,k)-E1,2-E2,3由子圖C2與Col(3∶ 1)兩部分組成，而且C2和Col(3∶ 1)中各包含1條故障邊，同情況1一致。

綜上所述，Torus(k,k)-F是Hamiltonian.

參考文獻(xiàn)：

[1] ZHU X，HUANG Z，ZHANG J，et al.Granular computing based intrusion detection model upon network monitor data streams[C]∥Pervasive Computing and Applications，Nanjing.2007：414-418.

[2] LI W.Using genetic algorithm for network intrusion detection[C]∥Proceedings of the United States Department of Energy Cyber Security Group，Mississippi State.2004：1-8.

[3] FARAOUN K M，BOUKELIF A.Neural networks learning improvement using the K-means clustering algorithm to detect network intrusions[J].International Journal of Computational Intelligence，2006，3(2)：161-168.

[4] LEE S C，HEINBUCH D V.Training a neural-network based intrusion detector to recognize novel attacks[J].IEEE Transactions on Systems，Man and Cybernetics，2001，31(4)：294-299.

[5] OH S H，KANG J S，BYUN Y C，et al.Intrusion detection based on clustering a data stream[C]∥Software Engineering Research，Management and Applications，South Korea.2005：220-227.

[6] 馬雪，原軍，張憲敏.容錯(cuò)元立方體的邊泛圈性[J].太原科技大學(xué)學(xué)報(bào)，2013，34(5)：398-400.

[7] PARK J H，KIM H C.Fault-hamiltonicity of product graph of path and cycle[M].Computing and Combinatorics.Springer Berlin Heidelberg，2003.

[8] KIM H C，PARK J H.Fault hamiltonicity of two-dimensional torus networks[C]∥Proc of Workshop on Algorithms and Cmputation WAAC'00，Tokyo.2000：110-117.

[9] XIANG Y，STEWART I A.Bipancyclicity in k-ary n-cube with faulty edges under a conditional fault assumpition[J].IEEE.Transactions on Parallel and Distributed Systems，2011，22(9)：1506-1513.

[10] 王世英，李晶，楊玉星.互連網(wǎng)絡(luò)的容錯(cuò)嵌入[M].北京：科學(xué)出版社，2012.