匹配組合網(wǎng)絡(luò)的寬直徑①

高珊

（湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430062）

圖的很多參數(shù)，如連通度和直徑，在圖論和組合數(shù)學(xué)本身十分重要，而且由于與通信網(wǎng)絡(luò)的容錯性和傳輸延遲密切關(guān)聯(lián)而被廣泛研究.當(dāng)前，隨著超大規(guī)模集成電路技術(shù)和光纖材料科學(xué)的發(fā)展，針對大規(guī)模并行處理和圖論算法的需要，一些學(xué)者致力于研究圖的寬直徑，力求設(shè)計(jì)出稀疏、均勻且具有盡可能小的直徑和盡可能大的連通度的網(wǎng)絡(luò)，以提高互連網(wǎng)絡(luò)的可靠性、容錯性，減小網(wǎng)絡(luò)的通信延遲，并取得了一些較好的研究結(jié)果.筆者研究匹配組合網(wǎng)絡(luò)G(G0,G1;M)的寬直徑，并根據(jù)該網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)，用點(diǎn)不交的最短路徑方法得到G(G0,G1;M)的寬直徑的上界估計(jì)式.

1 定義及預(yù)備定理

采用Bondy和Murty[1]中的術(shù)語和記號，并且只考慮簡單無向圖.我們用G=(V,E)表示一個(gè)圖，令u∈V(G)，NG(u)和dG(u)分別表示點(diǎn)u的鄰域和度.圖G中兩點(diǎn)u和v的距離dG(u,v)，定義為G的最短(u,v)-路的長度，如果沒有這樣的路存在，則令dG(u,v)=∞.圖G的直徑d(G)定義為G中任意兩點(diǎn)之間的最大距離.如果圖G不是完全圖Kn，那么G的連通度κ(G)定義為G中所有點(diǎn)分離集的最小頂點(diǎn)數(shù)，否則κ(Kn)=n-1.如果κ(G)≥k，那么G稱為k-連通的.

若一個(gè)圖G是k-連通的，則由Menger定理可知，對G中任何不同兩頂點(diǎn)u和v，G中存在k條點(diǎn)不交的(u，v)-路.

令G為ω-連通的，且0＜k≤ω.圖G的寬直徑及相關(guān)的概念定義如下：

定義1[2]對G中任何不同兩頂點(diǎn)u和v，圖G中從u到v的寬度為k的距離，簡稱k-距離，記為dk(G;u,v)，定義為最小整數(shù)d.換句話說，dk(G;u,v)是一個(gè)最小正整數(shù)d使得G中至少存在k條內(nèi)點(diǎn)不交且長不超過d的(u,v)路.

定義2[2]圖G的寬度為k的直徑，簡稱k-直徑，記為dk(G)，定義為dk(G)=max{dk(G;u,v):?u,v∈V(G)},

顯然，d1(G)就是G的直徑d(G)，而且有d(G)=d1(G)≤d2(G)≤…≤dω-1(G)≤dω(G).

寬直徑的概念最先是由Hsu[3]，Hsu和Lyuu[4]，Hsu和Luczak[5]，F(xiàn)landrin和Li[6]提出的.寬直徑是度量互聯(lián)網(wǎng)絡(luò)容錯性的重要參數(shù)，也是圖論的重要研究方向.一些圖的寬直徑，例如笛卡爾乘積圖等已被研究[1，3，6-9].

對一般圖G，給出dk(G)的值是困難的，因?yàn)檫@是NP完備問題.目前，只得到了一些dk(G)的上下界的估計(jì)式和一些著名的圖（結(jié)構(gòu)簡單）的寬直徑.

下面我們也需要給出網(wǎng)絡(luò)傳輸延遲和容錯性的另一種類型的度量參數(shù)——Rabin數(shù).

定義3設(shè)G是ω(≥ 1)連通圖，圖G的ω-Rabin數(shù)，記為rω(G)，定義為最小數(shù)r，使得對G的任何ω+1個(gè)頂點(diǎn)x,y1,…,yω，G中存在ω條內(nèi)點(diǎn)不交且長度不超過r的(x,yi)路，i=1,2,…,ω.即G中存在扇Fω(x,Y)，使得每條路的長度至多為r，其中Y={y1,…,yω} .

顯然，如果1≤ω≤κ(G)，則rω(G)有確定的值，且d(G)=r1(G)≤r2(G)≤…≤rω-1(G)≤rω(G).

2 匹配組合網(wǎng)絡(luò)G(G0,G1;M )

令r和n都是正整數(shù)，且r≥3.令G0和G1是兩個(gè)圖，且|V(G0)|=|V(G1)|=n.圖G(G0,G1;M)的 頂 點(diǎn) 集 定 義 為V(G0)?V(G1)，邊集為E(G0)?E(G1)?M，其中M是G0和G1頂點(diǎn)間的一個(gè)任意完美匹配（見圖1）.則G(G0,G1;M)是一個(gè)頂點(diǎn)數(shù)為2n，邊數(shù)為|E(G0)|+|E(G1)|+n，具有完美匹配的圖.例如，若G0=G1=Qk，則存在M使得G(G0,G1;M)=Qk+1；或者若G0=G1=CQk，則存在M使得G(G0,G1;M)=CQk+1，這里Qk表示k-維超立方體(hypercube)，CQk表示k-維交叉超立方體(crossed hypercube).

圖1 G0和G1頂點(diǎn)間的匹配圖

許多著名的網(wǎng)絡(luò)，例如超立方體、螺旋立方體、星圖等等，能通過連接兩個(gè)低維的網(wǎng)絡(luò)擴(kuò)展為高維的網(wǎng)絡(luò)，下面的匹配組合網(wǎng)絡(luò)就是這樣的擴(kuò)展例子[7-8].

圖G的一個(gè)完美匹配就是邊的集合M，滿足沒有兩條邊是有公共頂點(diǎn)的，并且G中的每個(gè)頂點(diǎn)都在M中.顯然，如果圖G有完美匹配，那么圖G的階一定是偶數(shù).

本文中將討論分析匹配組合網(wǎng)絡(luò)G(G0,G1;M)的寬直徑.為了方便，下面用u→Pk v表示從u到v的路Pk，u→v表示邊uv.

3 網(wǎng)絡(luò)G(G 0,G1;M )的寬直徑

為了簡單起見，下面我們把G(G0,G1;M)，V(G0)，V(G1)分別簡記為G,V0,V1.對任意的點(diǎn)u∈V(G)=V0?V1，即u∈Vi(i=0,1) ，用uˉ∈V1-i表示與u相鄰的頂點(diǎn).顯然，有uuˉ∈M.

定理3.1令G0和G1是兩個(gè)頂點(diǎn)數(shù)相同的連通圖，且κ(G0)=κ(G1)=ω，那么κ(G)≥ω+1.

定理3.1的證明由Menger-Whitney判定準(zhǔn)則，我們只需在G中構(gòu)造ω+1條內(nèi)點(diǎn)不交的(u,v)-路R1,…,Rω,Rω+1.對于圖G的任意兩點(diǎn)u和v，不妨假設(shè)u∈V0.我們考慮兩種情形.情形1v∈V0.

因?yàn)镚0是ω-連通的，故由Menger定理可知，G0中存在ω條內(nèi)點(diǎn)不交的( )u,v- 路P1,P2,…,Pω.另一方面，G1中存在一條(),ˉ- 路 Q.令

則R1,…,Rω,Rω+1是G中內(nèi)點(diǎn)不交的路.

情形2v∈V1.

令U?Vi{u} ，V?V1-i{v}，其中U={u1,u2,…,uω} ，V={v1,v2,…,vω} .因?yàn)镚0和G1是ω- 連通的，Gi中存在(U,u)- 扇Fω(U,u)={W1,W2,…,Wω} ，其中Wk的長度最多為rω(Gi)；G1-i中存在 (V,v)-扇Fω(V,v)={T1,T2,…,Tω} ，其中Tk的長度最多為rω(G1-i).

如果v=ˉ，那么我們選擇U，V使得vvk∈E(G1-i) ，vk=，其中k=1,2,…,ω.令

否則，我們選擇U，V使得其中k=1,2,…,ω-1.令

易驗(yàn)證，上述情形中構(gòu)造的路R1,…,Rω,Rω+1是G中內(nèi)點(diǎn)不交的路.證畢.

推論3.2令G0和G1是頂點(diǎn)數(shù)相同的兩個(gè)圖，G=G(G0,G1;M).如果κ(G0)=κ(G1)=δ(G0)=δ(G1)=ω，那么

推論3.2的證明由定理3.1，有κ(G)≥ω+1.由Whitney不等式，可以得到

因此，κ(G)=ω+1.證畢.

定理3.3令G0和G1是頂點(diǎn)數(shù)相同的兩個(gè)圖，G=G(G0,G1;M).如果κ(G0)=κ(G1)=δ(G0)=δ(G1)=ω，其中i=0,1，那么dω+1(G)≤max{2 +rω(G0),2+rω(G1),dω(G0),dω(G1) }.

定 理3.3的 證 明由 推 論3.2，G是(ω+1)- 連 通 的.因 此dω+1(G)有 確 定 的 值.令d=和v是G中不同兩個(gè)頂點(diǎn).下面，我們只需在G中構(gòu)造(ω+1)條長度不超過d的內(nèi)點(diǎn)不交的(u,v)-路.

情形1u,v∈Vi(i∈{0 ,1}).

圖2 G0，G1關(guān)系示意圖

因?yàn)镚i是ω-連通的，由Menger定理，Gi中存在ω條內(nèi)點(diǎn)不交的(u,v)-路P1,P2,…,Pω，使得Pk(1 ≤k≤ω)的最大長度為dω(Gi).令Q是G1-i中最短(uˉ ,vˉ)- 路(參見圖 2)，

則由rω(Gi)≥d(Gi)可知，

情形2u∈Vi，v∈V1-i.

令

則

如果v≠uˉ，那么G1-i中存在一條最短路假設(shè)v1在Q上.令則因?yàn)镚i是ω- 連通的，Gi中存在 (U,u)-扇Fω(U,u)=其中Wk的長度最多為rω(Gi) ，參數(shù)關(guān)系見圖3（b）.

則由rω(Gi)≥d(Gi)可知，

證畢.

本文中主要討論了匹配組合網(wǎng)絡(luò)的寬直徑.匹配組合網(wǎng)絡(luò)是著名的互連網(wǎng)絡(luò)，給出了組合匹配網(wǎng)絡(luò)G( )G0,G1;M的寬直徑的上界，為度量該網(wǎng)絡(luò)的性能提供了重要的依據(jù).

圖3 G0，G1匹配組合網(wǎng)絡(luò)圖

[1]Bondy JA，Murty USR.Graph theorywith applications[M].London:Macmillan，1976.

[2]徐俊明.組合網(wǎng)絡(luò)理論[M].北京：科學(xué)出版社，2007：241.

[3]Hsu DH.On container width and length in graphs，groups，and networks[J].IEICE Trans Fundam，1994，E77A:668-680.

[4]Hsu D H，Lyuu Y D.A graph-theotetical study of transmission delay and fault tolerance[C].In Proc of 4thISMM International Confrenceon Paralleland Distributed Computingand systems，1994.

[5]Hsu DH，Luczak T.Noteon thek-diameterofk-regulark-connected graphs[J].DiscreteMath，1994，132:291-296.

[6]Flandrin E，LiH.Mengerian properties，Hamiltonicity and claw-free graph[J].Networks，1994，24:660-678.

[7]Chen Y，Jimmy JM.Tan Restricted connectivity for three familiesof interconnection networks[J].Appl Math Comput，2007，188:1848-1855.

[8]Chen Y，Jimmy J，Tan M，etal.Super-connectivity and super-edge-connectivity for some interconnection networks[J].Appl Math Comput，2003，140:245-254.

[9]BanicˇI，?erovnik J.Wide diameter of Cartesian graph bundles[J].Discrete Math，2010，310:1697-1701.