二維環(huán)面網(wǎng)絡(luò)的一對多不交覆蓋路

左淑榕,李 晶,李旭璟

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

隨著社會的進步，計算機技術(shù)的高速發(fā)展讓規(guī)模大、復(fù)雜度高的互連網(wǎng)絡(luò)成為現(xiàn)實，這些互連網(wǎng)絡(luò)已經(jīng)成為廣播網(wǎng)絡(luò)、局域網(wǎng)絡(luò)、通信網(wǎng)絡(luò)以及其他分布式計算機系統(tǒng)設(shè)計中的核心，且在大規(guī)模并行系統(tǒng)中扮演著不可缺少的角色，同時決定著整個系統(tǒng)的安全性，實用性和可靠性。

Torus網(wǎng)絡(luò)是目前應(yīng)用最廣的分布式計算機系統(tǒng)互連網(wǎng)絡(luò).例如 iWarp[1]，Cray X1向量機和惠普GS1280[2]都以二維Torus網(wǎng)絡(luò)作為互連網(wǎng)絡(luò)拓撲.在互連網(wǎng)絡(luò)頂點之間尋找不交路是網(wǎng)絡(luò)拓撲研究中經(jīng)典問題之一，因為不交路問題與網(wǎng)絡(luò)數(shù)據(jù)傳遞密切相關(guān).近年來，學(xué)者們對Torus網(wǎng)絡(luò)的不交路覆蓋問題進行了廣泛研究.例如，Kim和Park證明了當ki≥3是奇數(shù)時,T(k1,k2)是哈密爾頓連通的(即一對一不交路覆蓋)，其中i=1,2[3].隨后又證明了T(k1,k2)是二對二不交路覆蓋的,其中k1,k2≥3[4].然而,不交路覆蓋問題中的一對多問題尚未有人進行研究,本文將對Torus網(wǎng)絡(luò)的這一問題進行討論。

1 預(yù)備知識

一個二維m×n的環(huán)面(以下簡記為T(m,n) 其中m,n≥3)是由mn個頂點構(gòu)成，且每個頂點用vi,j表示，其中1≤i≤m,1≤j≤n.任意兩個不同的頂點va,b和va′,b′相鄰當且僅當a=a′±1,b=b′或者a=a′,b=b′±1.對于每個邊(vi,1,vi,n)稱為行環(huán)繞邊，對于每個邊(v1,j,vm,j)稱為列環(huán)繞邊.將T(m,n)的所有列環(huán)繞邊刪去所生成的圖記作Row-T(m,n)，將T(m,n)所有行和列環(huán)繞邊刪去所生成的圖記作Grid(m,n).圖1展示了T(3,4)和Row-T(3,4).當m≥2且n≥2時，定義R*(m,2n+1)=Row-T(m,2n+1)-v1,1，圖2為R*(3,5).

圖1 T(3,4)和Row-T(3,4)

圖2 R*(3,5)

設(shè)G是T(m,n)或Row-T(m,n).Row(a:b)是由{vi,j:a≤i≤b,1≤j≤n}生成的G的子圖，簡寫為R(a:b)，Col(a:b)是由{vi,j:1≤i≤m,a≤j≤b}生成的G的子圖，簡寫為C(a:b).R(a:a)和C(a:a)可以分別用R(a)和C(a)來表示。

一對一不交覆蓋路指的是連接一個匯點和一個源點之間的,覆蓋圖中所有頂點的不交路。一對多不交路是指連接一個源點和多個匯點之間的覆蓋圖中所有頂點的不交路。而多對多不交路是指連接多個源點和多個匯點之間的覆蓋圖中所有頂點的不交路。目前這三種類型都在不交路的覆蓋問題中得到了廣泛的研究。本文主要探討了二維環(huán)面網(wǎng)絡(luò)中的一對多不交路覆蓋問題。下面給出證明中將用到的引理：

引理1T(k1,k2)是哈密爾頓連通的，其中ki≥3是奇數(shù)，i=1,2[3].

引理2Row-T(m,2n+1)，m≥2,n≥1，是哈密爾頓連通的[3]。

引理3R*(m,2n+1)，m≥3,n≥2，中最后一行中任意兩個相鄰頂點間有哈密爾頓路[5]。

下面的兩個引理是顯然的。

引理4R*(2,2n+1)，n≥1，中頂點v2,1與v2,2(或頂點v2,1與v2,2n+1)之間存在哈密爾頓路。(見圖3)

圖3 引理4證明

引理5Grid(m,n)中，位于第一行的任意相鄰頂點之間存在哈密爾頓路，其中m,n≥2且n為偶數(shù)。

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

定理1對任意整數(shù)1≤m≤3，二維Torus網(wǎng)絡(luò)T(k1,k2)是一對多m不交路覆蓋的，其中k1,k2≥5是奇數(shù)。

證明：當m=1時，由引理1知結(jié)論成立。

當m=2時，假設(shè)有一個源點a和兩個匯點b和c.由引理1知，b和c之間存在一條哈密爾頓路，此時點a是這條路上的中間節(jié)點.由此，這條路上的a到b的一段和a到c的一段構(gòu)成了一個一對二不交路覆蓋，故結(jié)論成立。

下面設(shè)m=3，構(gòu)建一對三不交路覆蓋。

不失一般性可設(shè)s=v1,1是源點，T={a,b,c}是匯點集。

情形1存在整數(shù)r，可將T(k1,k2)按列分成兩部分C(1:r)和C(r+1:k2)，使得C(1:r)包含兩個匯點，C(r+1:k2)有一個匯點，且C(1:r)和C(r+1:k2)都至少有兩列。

此時，不妨設(shè)a,b∈C(1:r)，c∈C(r+1:k2)，注意到C(1:r)同構(gòu)于Row-T(r,k1)，這里r≥2且k≥5是奇數(shù).由引理2知，C(1:r)中有一條哈密爾頓路連接點a和b，此時源點s是這條路上的中間點，記(s,a)段為P1，(s,b)段為P2，設(shè)x是點s在C(k2)中的對應(yīng)點，即x=v1,k2.

情形1.1當x≠c.

由于C(r+1:k2)同構(gòu)于Row-T(k2-r,k1)，此時k2-r≥2且k1≥5是奇數(shù)，故由引理2知，在C(r+1:k2)中，點x和c之間存在一條哈密爾頓路P.如圖4所示.令P3=〈s,x,P,c〉，則〈P1,P2,P3〉構(gòu)成T(k1,k2)的一對多3不交路覆蓋(簡稱3-DPC).

情形1.2x=c且C(r+1:k2)中至少有3列。

由于C(r)同構(gòu)于一條長為k1的圈，k1≥5，故在圖C(1:r)中，可選取C(r)上一個點d，使得d?{a,b}，可見d是路P1或P2上的中間點，不妨設(shè)d∈P1(情形d∈P2的證明是類似的).因為d在C(1:r)中的度為3，有3條邊與它關(guān)聯(lián)，其中兩條在C(r)上，又因為d與P1上兩條邊相關(guān)聯(lián)，故C(r)上至少有一條與d相關(guān)聯(lián)的邊在P1上，記為(d,e)，設(shè)(d,e)在C(r+1)上的對應(yīng)邊為(d′,e′)，如圖5所示，注意到C(r+1:k2)-x同構(gòu)于R*(k2-r,k1)，由引理3可知，C(r+1:k2)-x中有從d′到e′的哈密爾頓路P，令P1′是從P1上將(d,e)替換成〈d,d′,P,e′,e〉而得，P3=〈s,c〉，則〈P1′,P2,P3〉為所求的一對多3-DPC.

情形1.3x=c且C(r+1:k2)中恰有兩列。

此時，C(1:r)=C(1:k2-2)，C(r+1:k2)=C(k2-1:k2)，v1,k2=c=x。同樣，在C(r)上找到點v1,k2-2.

若v1,k2-2?{a,b}，則v1,k2-2是P1或者P2的中間點,不妨設(shè)在P1上.令d=v1,k2-2，進而在C(k2-2)上與d相關(guān)聯(lián)的兩條邊必有一條在P1上.設(shè)這條邊為(d,e).若e=v2,k2-2，在C(r+1:k2)中，點v1,k2-1和v2,k2-1分別是點d和e的對應(yīng)點.由于C(k2-1:k2)-x同構(gòu)于R*(2,k1)，由引理4，在C(k2-1:k2)-x中存在一條連接點v1,k2-1和v2,k2-1的哈密爾頓路P.和情形1.2一樣，令P1′是從P1上將(d,e)替換成〈d,v1,k2-1,P,v2,k2-1,e〉而得，P3=〈s,c〉，則〈P1′,P2,P3〉為所求的一對多3-DPC.若e=vk1,k2-2，同上述情形相仿，可得一對多3-DPC.

若v1,k2-2∈{a,b}，不妨設(shè)v1,k2-2=a，將T(k1,k2)重新分為兩部分R(1)和R(2:k1)，此時s=v1,1，a=v1,k2-2，c=v1,k2，并且兩點均在R(1).討論點b.

若點b∈R(1)，那么所有的源點和匯點均在R(1).分兩種情況：

若a和b相鄰，如圖6(a)所示,由于R(2:k1)同構(gòu)于Row-T(k1-1,k2)，k2為奇數(shù)且k2≥5，由引理2知，R(2:k1)中存在一條哈密爾頓路P連接點v2,1和點v2,k2-1.令P1′=〈s,v2,1,P,v2,k2-1,v1,k2-1,a〉，P2′=〈s,v1,2,…,b〉，P3′=〈s,c〉，則〈P1′,P2′,P3′〉構(gòu)成了一對多3-DPC.

圖6 情形1.3

情形2存在整數(shù)r使得可以將T(k1,k2)按行分成兩部分：R(1:r)和R(r+1:k1)，使得R(1:r)包含s和兩個匯點，R(r+1:k1)包含1個匯點，且兩部分都至少有兩行。

由Torus網(wǎng)絡(luò)的對稱性，由情形1可知結(jié)論成立。

情形3情形1和情形2不成立。

情形3.1若三匯點分別位于不同列.此時總是可以找到一個C(1:r)包含兩個匯點C(r+1:k2)包含一個匯點.當每一個部分均至少包含兩列時,這種情況類似情形1.否則，C(r+1:k2)僅包含一列，這意味著C(k2-1)和C(k2)均分別含有一個匯點.若C(1)沒有匯點，將T(k1,k2)重新分成兩部分C(k2-1:1)和C(2:k2-2).注意到C(k2-1:1)含有兩個匯點，C(2:k2-2)含有一個匯點，其均至少包含兩列.同樣的，這種情況類似于情形1;若C(1)有匯點，將T(k1,k2)重新分成兩部分C(k2:1)和C(2:k2-1).注意到C(k2:1)含有兩個匯點，C(2:k2-1)含有一個匯點，且均至少包含兩列.同樣的，這種情況類似于情形1。

情形3.2若三匯點分別位于不同三行。

同理這種情況類似于情形3.1。

情形3.3有兩個匯點位于同一列同時有兩個匯點位于同一行。

情形3.3.1 第一列 (或第一行)有2個匯點。

不妨設(shè)第一列有2個匯點，此時，無論第3個匯點位于哪一列，都有情形1成立，故得證。

情形3.3.2 第一列 (或第一行)恰有1個匯點。

不失一般性，設(shè)第一列有1個匯點b，另2個匯點a,c在第r列.當?shù)谝恍袥]有匯點時，考慮到情形1和情形2不成立，故點b是確定的即b=vk1-1,1，設(shè)與點b位于同一行的是點c，當另一匯點a位于點c上方時，將其按行劃分為R(k1-1:1)與R(2:k1-2)，此時R(k1-1:1)包含兩個匯點，R(2:k1-2)包含一個匯點，且兩部分均至少包含兩行，與情形1類似，可得一對多3-DPC.當點a位于點c下方時，則有{a,b,c}={vk1,r,vk1-1,1,vk1-1,r}，當r≠k2時，如圖7(a)所示，C(r+1:k2)同構(gòu)于Row-T(k2-r,k2)，k2-r≥2，故由引理2得，點v1,k2到點vk1,r+1存在一條哈密爾頓路H，令P1=〈s,v1,k2,H,vk1,r+1,a〉，P2=〈s,vk1,1,…,vk1,r-1,vk1-1,r-1,vk1,r-2,…,b〉，P3=〈s,v1,2,…,v1,r,v2,r,v2,r-1,…,v2,1,v3,1,…,vk1-2,r,c〉，即得一對多3-DPC；當r=k2時，如圖7(b)所示，將其按行劃分為R(1:k1-1)和R(k1)，R(1:k1-1)為Row-T(k1-1,k2)，由引理2得，點b和c存在哈密爾頓路且源點s為其中一點，同情形1類似，可得一對多3-DPC.

圖7 情形3.3.2

圖8 情形3.3.2

圖9 情形3.3.3

情形3.3.3 第一列和第一行都沒有匯點。

由于C(1)沒有匯點，此時考慮到情形1不成立，則由對稱性不妨設(shè)C(k2-1)包含兩個匯點，C(k2)有一個匯點.又考慮到情形2不成立，則存在兩種情況：(1)R(k1-1)含有兩個匯點，R(k1)含有一個匯點；(2)R(2)含有一個匯點，R(3)含有兩個匯點.若前者成立，則{a,b,c}={vk1-1,k2-1,vk1,k2-1,vk1-1,k2}，如圖9(a)所示，一個一對多3-DPC是可以建立的.若后者成立，則{a,b,c}={v2,k2-1,v3,k2-1,v3,k2}，按圖9(b)所示同樣可以構(gòu)造一個一對多3-DPC，其中H是C(1;k2-2)中從點v1,k2-2到點vk1,k2-2的哈密爾頓路。

綜上所述，T(k1,k2)是一對多3-DPC的，證畢。