帶故障邊的路和圈的笛卡爾乘積圖的哈密爾頓路

姜瓔哲,李 晶

(太原科技大學 應用科學學院,太原 030024)

在并行計算機系統(tǒng)中并行處理的核心問題之一是如何將線性陣列和環(huán)嵌入其底層互連網(wǎng)絡拓撲中。嵌入是一個拓撲結(jié)構(gòu)到另一個拓撲結(jié)構(gòu)的映射,嵌入線性陣列和環(huán)與圖論中的路和圈嵌入問題密切相關(guān)[1]。哈密爾頓路和圈的嵌入研究是互連網(wǎng)絡拓撲性質(zhì)研究的熱點之一。

近年來,關(guān)于互連網(wǎng)絡的容錯哈密爾頓路和圈的嵌入問題的研究,學者們已經(jīng)在各種互連網(wǎng)絡上取得了很多相關(guān)成果:Chen等[2]提出了在m×n網(wǎng)格中尋找哈密頓路的線性時間算法;Park等[3]證明了具有一條故障邊的笛卡爾乘積圖Pm×Cn中,任意兩個不同部中頂點u、v之間存在一條哈密爾頓路,其中m≥2,n≥4且n是偶數(shù)?；谠摻Y(jié)果,學者們獲得了有關(guān)二維和高維路和圈的笛卡爾乘積圖的哈密爾頓路圈嵌入問題的一系列結(jié)論[4-5]。在文獻[3]中,作者同時也證明了無故障Pm×Cn(n≥3且是奇數(shù))是哈密爾頓連通的。然而,對具有一條故障邊的Pm×Cn卻沒有類似的結(jié)論。本文就這一情況進行進一步探討,對當m≥3且n≥5是奇數(shù)時,具有一條故障邊的Pm×Cn的哈密爾頓路的存在情況進行刻畫。通過對故障邊位置的不同,對Pm×Cn中的哈密爾頓路的存在情況進行了討論并得到3個相關(guān)結(jié)論。本文主要結(jié)論對具有一條故障邊的笛卡爾乘積圖Pm×Cn的哈密爾頓路問題進行了補充。同時,這些結(jié)論可以用作討論高維奇圈笛卡爾乘積圖的容錯哈密爾連通性的歸納基礎。

1 預備知識

路和圈的笛卡爾乘積圖(簡記為Pm×Cn)是由mn個頂點構(gòu)成的。Pm×Cn的頂點集V={vij|1≤i≤m,1≤j≤n},邊集E={Er∪Ec},其中,Er={(vij,vi,j+1)|1≤i≤m,1≤j≤n}∪{(vin,vi1|1≤i≤m},Ec={(vij,vi+1,j)|1≤i

圖1 P3×C5

圖2 M(3,5)和M2(3,5)

令G=Pm×Cn,定義R(i)與C(j)分別為第i行、第j列的點導出的G的子圖,即R(i)=G{vij|1≤j≤n}、C(j)=G{vij|1≤i≤m}.令R(i∶i′)=G{vkj|i≤k≤i′,1≤j≤n},否則R(i∶i′)=φ.同樣地,令C(j∶j′)=G{vik|1≤i≤m,j≤k≤j′},否則C(j,j′)=φ.顯然,R(i∶j)與Pi-j+1×Cn同構(gòu),C(∶j)與Pj-1+1×Cm同構(gòu)。包含Pm×Cn的每個頂點的路稱為Pm×Cn的Hamilton路;類似地,Pm×Cn的Hamilton圈是指包含Pm×Cn的每一個頂點的圈。

為了方便證明,當i+j為奇數(shù)時稱Pm×Cn中頂點vij為奇點;當i+j為偶數(shù)時稱vij為偶點。定義集合[R1∶R2]={e|e∈(v1i,v2,i),1≤i≤m};[Rm-1∶Rm]={e|e∈(vm-1,i,vm,i),1≤i≤m}.

下面給出圖Pm×Cn和M2(m,n)的兩個性質(zhì),這些性質(zhì)將在證明中被用到。

引理1[6]圖M2(m,n)是哈密爾頓連通的,其中m≥2,n≥3且n是奇數(shù)。

引理2[7]圖Pm×Cn是哈密爾頓連通的,其中m≥2,n≥3且n是奇數(shù)。

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

設f是Pm×Cn中一條故障邊,其中m≥3且n≥5是奇數(shù)。根據(jù)故障邊f(xié)的不同位置,分以下幾種情況討論。

引理1若f是一條列邊,且f?[R1∶R2]∪[Rm-1∶Rn],則Pm×Cn-f是哈密爾頓連通的。

證明因為f是一條列邊,且f?[R1∶R2]∪[Rm-1∶Rn],所以m≥4.不妨設f=(vi1,vi+1,1).令G1=R(1∶i),G2=R(i+1∶m).

注意到G1同構(gòu)于Pi×Cn,G2同構(gòu)于Pm-i×Cn,且i≥2,m-i≥2.由引理2,G1和G1都是哈密爾頓連通的。

設u、v是Pm×Cn-f中任意兩個頂點,根據(jù)這兩個點的位置,分兩種情況討論。

情形1u、v∈G1或u、v∈G2

由對稱性,只需討論u、v∈G1.因為G1是哈密爾頓連通的,所以在G1中存在從u到v的哈密爾頓路,設為P1.

因為n≥5,所以在R(i)上,除點u、v、vi1外,至少還有兩個點,都是P1上的中間點。注意到這些點在G1中都與三條健康邊關(guān)聯(lián),且其中兩條都在R(i)上,故存在一個點vij,vij≠vi1,在R(i)上的關(guān)聯(lián)邊(v)ij,vi,j+1)也在P1上。

因為G2是哈密爾頓連通的,所以在G2中存在從vi+1,j到vi+1,j+1的一條哈密爾頓路P2.令P*=〈vij,vi+1,j,P2,vi+1,j+1,vi,j+1〉,則P1∪P*-(vij,vi,j+1)即為一條u到v的哈密爾頓路。見圖3.

圖3 引理1中情形1

情形2u∈G1,v∈G2

設vij是G1中R(i)上的點,滿足vij≠u,vij≠vi1,且vi+1,j≠v.則G1有一條從u到vij的哈密爾頓路P1,G2有一條從vi+1,j到v的哈密爾頓路P2,即P=〈u,P1,vij,vi+1,j,P2,v〉為所求哈密爾頓路。見圖4.

圖4 引理1中情形2

證畢。

在給出引理2之前,首先給出一個例子。在圖P3×C5中,邊(v11,v21)是一條故障邊,由于此時v11僅與兩條健康邊關(guān)聯(lián),則v12和v15之間不可能有哈密爾頓路。如圖5.

圖5 不存在從點v12到點v15的哈密爾頓路的實例

引理2若f是一條列邊,且f∈[R1∶R2]∪[Rm-1∶Rn],則除了一種情況外,Pm×Cn-f是哈密爾頓連通的。

證明不失一般性設f=(v11,v21)∈[R1∶R2],顯然Pm×Cn-f中不存在從點v12到v1n的哈密爾頓路。下證除這兩點外,其余任意兩點u、v之間仍然存在哈密爾頓路。

令G1=R(1),G2=R(2∶m).因為G2同構(gòu)于Pm-1×Cn,且m-1≥2.由引理2,G2是哈密爾頓連通的。

情形1u、v∈G2

因為G2是哈密爾頓連通的,故G2有一條哈密爾頓路P1連接u、v,在R(2)上不難找到一條邊e,使得e∈E(P1)且e不與v21關(guān)聯(lián)。記e=(v2j,v2,j+1).令P2=Row(1)-(v1j,v1,j+1),則P=P1∪P2-e為所求哈密爾頓路。

情形2u∈G1,v∈G2

情形2.1u?{v11,v12}

記u=v1j,則u在R(1)上的兩個鄰點為v1,j-1,v1,j+1.這兩個鄰點都與f不關(guān)聯(lián)且至少有一個在R(2)上的對應點不是v,不妨設v1,j-1滿足條件。令P1=R(1)-(v1,j-1,u).顯然,P1是G2中的哈密爾頓路,令P2是G2中一條從v2,j-1到v哈密爾頓路。則P=〈u,P1,v1,j-1,v2,j-1,P2,v〉為所求的哈密爾頓路,如圖6.

圖6 引理2中情形2.1

情形2.2u=v11

當v≠v2n時,如圖7(a)所示,令P1=R(1)-(u,v1n),P2是G2中一條從v2n到v哈密爾頓路。則〈u,P1,v1n,v2n,P2,v〉即為所求哈密爾頓路。

圖7 引理2中情形2.2

當v=v2n時,如圖7(b)所示,在R(1∶2)-f中構(gòu)造一條哈密爾頓路P1=〈u,v1n,v1,n-1,v2,n-1,v2,n-2,v1,n-2,…,v12,,v22,v21,v〉.此時,在R(3∶m)中存在連接v31到v32的哈密爾頓路P2.令P*=〈v21,v31,P2,v32,v22〉,此時,P=P1∪P*-(v21,v22)即為所求哈密爾頓路。

情形2.3u=v12

當v≠v23,令P1=R(1)-(v12,v13),P2是G2中從v23到v哈密爾頓路。則〈u,P1,v13,v23,P2,v〉即為所求哈密爾頓路。

當v=v23時,首先考慮m=3的情況。如圖8所示,令P1=.可見P1經(jīng)過了R(1∶2)中除v21,v22以外所有的點。令P2=〈v2,n-1,v3,n-1,v3,n-2,…,v32,v22,v21,v31,v3n,v2n〉.可見P2包含了R(3)上所有頂點和路P1未包含的點v21,v22.即P1∪P2-(v2,n-1,v2n)是連接u、v的哈密爾頓路。

圖8 引理2中情形2.3 v=v23

當m≥4時,記上面構(gòu)造的哈密爾頓路為P3,從R(3)∩P3上取一條邊(v3j,v3,j+1)。由引理2知R(4∶m)中存在連接v4j、v4,j+1的哈密爾頓路P4,此時,將P3上的邊(v3j,v3,j+1)用P4替換,可得到所求的哈密爾頓路。

情形3u、v∈G1

情形3.1u、v相鄰

令P1=R(1)-(u,v).顯然,P1是G1中的哈密爾頓路。取P1上的邊(v1j,v1,j+1),用G2中一條從v2j到v2,j+1哈密爾頓路替換,即可得到所求的哈密爾頓路。

情形3.2u、v不相鄰,且u=v11

設v=v1j,j≠2,n,如圖9,令P1=〈u,v12,…,v1,j-1〉.因為G2是哈密爾頓連通的,故可設P2是G2中連接v2,j-1和v2n的哈密爾頓路。則〈u,P1,v1,j-1,v2,j-1,P2,v2n,v1n,v1,n-1,…,v〉即為所求的哈密爾頓路。

圖9 引理2中情形3.2

不妨設u=u1i,v=v1j,且i

當v≠v1n時,令P1=〈u,v1,i-1,…,v11,v1n,v1,n-1,…,v1,j+1〉,令P2是G2中從v2,j+1到v2,i+1的哈密爾頓路,則〈u,P1,v1,j+1,v2,j+1,P2,v2,i+1,v1,i+1,v1,i+2,…,v〉為所求的哈密爾頓路。見圖10(a).

圖10 引理2中情形3.3

當v=v1n時,注意此時u≠u12.令P1=〈u,v1,i+1,…,v1,n-1〉.令P2是G2中從v2,n-1到v2,i-1的哈密爾頓路,則〈u,P1,v2,n-1,P2,v2,i-1,v1,i-1,v1,i-2,…,v11,v〉為所求的哈密爾頓路。見圖10(b).

證畢。

定理1設f是Pm×Cn中一條故障邊,若f是一條列邊,則除一種情況外,Pm×Cn-f是哈密爾頓連通的,其中m≥3且n≥5是奇數(shù)。

下面兩個定理考慮f是行邊的情況。

定理2若f是一條故障行邊,且f?R(1)∪R(m),則Pm×Cn-f是哈密爾頓連通的,其中m≥3且n≥5是奇數(shù)。

證明注意到當f是一條行邊且f?R(1)∪R(m)時,圖M2(m,n)是Pm×Cn-f的生成子圖。由引理1,M2(m,n)是哈密爾頓連通的,故Pm×Cn-f是哈密爾頓連通的。

證畢。

定理3若f是一條故障行邊,且f∈R(1)∪R(m),則Pm×Cn-f中任意偶點與其他點之間存在哈密爾頓路,其中m≥3且n≥5是奇數(shù)。

情形1u、v∈G1

若點{u,v}≠{v1j,v2j},由于u是偶點,根據(jù)上面的討論知G1中有一條連接u、v的哈密爾頓路P1.在R(2)∩P1上取一條邊e1=(v2i,v2,i+1).令P2是G2中連接v3i和v3,i+1的哈密爾頓路。將P1上的e1用P2代替,可得到所求的哈密爾頓路。

首先構(gòu)造當m=3時的哈密爾頓路。當u=v1j且v=v2j時,其中j是奇數(shù),如圖11(a)所示,可構(gòu)造P3×Cn-f的哈密爾頓路。當u=v2j且v=v1j,其中j是偶數(shù)時,如圖11(b)所示,可構(gòu)造P3×Cn-f的哈密爾頓路。

圖11 定理3中情形1

接下來,若m≥4,則在P2∩R(3)取邊e2,用R(4∶m)上的哈密爾頓路代替e2,即可找到所求的從u到v的哈密爾頓路。

情形2u∈G1,v∈G2

若m≥4,在R(2)上找到一個點s,使得{u,s}≠{v1j,v2j},且s在在R(3)上的對應點不是v.令s=v2k,則G1中有從u到v2k的哈密爾頓路P1,G2中有從v3k到v的哈密爾頓路P2,連接P1和P2即為所求。

若m=3,則v∈R(3),且在R(3)上有兩個鄰點。選擇其中一個鄰點v3k使得v2k≠u且{u,v2k}≠{v1j,v2j}.則G1中有從u到v2k的哈密爾頓路P1,G2中有從v3k到v的哈密爾頓路P2,連接P1和P2即為所求。

情形3v∈G1,u∈G2

若m≥4,選取點v3k,其中k是偶數(shù),使得v2k≠v且{v,v2k}≠{v1j,v2j}.因為v3k是奇點,則v3k≠u.進而G2中有從u到v3k的哈密爾頓路P2.因為v2k是G1中的偶點,故G1中有從v2k到v的哈密爾頓路P1.連接P1和P2即為所求。見圖12(a).

圖12 定理3中情形3

若m=3,則u∈R(3),且在R(3)上有兩個奇鄰點。選擇其中一個奇鄰點v3k使得v2k≠v且{v,v2k}≠{v1j,v2j}.則G1中有從v2k到v的哈密爾頓路P1,G2中有從u到v3k的哈密爾頓路P2,連接P1和P2即為所求。見圖12(b).

情形4u、v∈G2

情形4.1m=3且u,v不相鄰

圖13 定理3中情形4.2

情形4.2m≥4或m=3且u,v相鄰

令P2是G2中連接u,v的哈密爾頓路。在R

證畢。