關于笛卡爾乘積圖邊容錯直徑的研究

劉啟云，王金建，謝 堃

(安徽大學數(shù)學科學學院，合肥 230601)

0 引言

大規(guī)模集成(VLSI)電路技術的出現(xiàn)，使人們能建造出非常龐大而復雜的互聯(lián)網(wǎng)絡.出于多方面考慮，下一代超級計算機系統(tǒng)將通過增加處理器的數(shù)目，而不是單靠利用更快的處理器來實現(xiàn)高速快捷的目的.建造超級計算機系統(tǒng)最困難的技術問題將是連接這些處理器的互聯(lián)網(wǎng)絡的設計，選擇一個合適和理想的互聯(lián)網(wǎng)絡拓撲結構將變成一個迫切需要解決的問題.實踐證明，圖論是設計和分析互聯(lián)網(wǎng)絡的最基本且強有力的數(shù)學工具，因為互聯(lián)網(wǎng)絡的拓撲結構就是圖.將網(wǎng)絡中的處理器看成圖中的頂點，各處理器之間的網(wǎng)絡連線對應于圖中連接相應頂點的邊，此時，就可以通過分析圖的結構來研究該網(wǎng)絡.這樣，網(wǎng)絡的建構方法和可靠性，就可以看作是圖的構造方法和可靠性.笛卡爾乘積是構建大型網(wǎng)絡的重要方法，容錯性是衡量網(wǎng)絡效用性的重要標準，它們均可對應成圖的相關特點和性質(zhì).

1 預備知識

介紹徐俊明［1］給出的圖的基本定義和符號，這里只考慮簡單無向圖，即那些沒有環(huán)和重邊的無向圖.

定義1 令圖G=(V(G)，E(G))，其中V(G)，E(G)分別是圖G的頂點集和邊集.對任何u，v∈V(G)，若u，v之間有邊，就說u和v是鄰接的，并分別用NG(u)，dG(u)表示頂點u的鄰點集合和鄰點的數(shù)目，通常dG(u)稱為u的度，圖G頂點的最小度和最大度記作δ(G)和Δ(G)，分別定義為

定義2 設u0，u1，…，uk是G中的k+1個不同的頂點，若對所有的0≤i≤k-1，均有ui與ui+1鄰接，記P=u0u1…uk，則P表示一條從u0到uk的路，其長度為k;距離dG(u，v)表示G中u到v最短路的長度，如果沒有這樣的路，就記dG(u，v)=∞.當u，v取遍所有的頂點，把dG(u，v)的最大值稱為圖G的直徑，記作d(G).

定義3G的點連通度κ(G)，指的是G的最小點割的大小，也就是說，存在V(G)的一個大小為κ(G)的子集，使得G在刪除這些點后變得不連通;相似地，邊連通度λ(G)指的是G的最小邊割的大小.

定義4 若κ(G)≥k，則說圖G是k點連通的;若λ(G)≥t，則說圖G是t邊連通的.

網(wǎng)絡的笛卡爾乘積設計在其拓撲結構上就是圖的笛卡爾乘積，接著描述一下徐俊明［3］給出的笛卡爾乘積圖構造方法及部分性質(zhì).

定義5 設G1=(V1，E1)和G2=(V2，E2)是兩個無向圖，G1和G2的笛卡爾乘積是無向圖，記為G1×G2，其中V(G1×G2)=V1×V2，兩個不同的頂點x1x2和y1y2(其中x1，y1∈V(G1)，x2，y2∈V(G2))相鄰當且僅當或者x1=y1且x2y2∈E(G2)，或者x2=y2且x1y1∈E(G1)，G1和G2稱為G1×G2的因子;若x1x2和y1y2鄰接，就用(x1x2，y1y2)或者(y1y2，x1x2)表示這條邊.

網(wǎng)絡的容錯性對應于它的圖結構的點容錯直徑和邊容錯直徑，徐俊明［3］也給出了相關的定義和結論.

定義6 對w點連通圖G，它的(w-1)點容錯直徑定義為

定義7 設G是t邊連通圖，x，y∈V(G)，F(xiàn)?E(G)，＜t;G中從x到y(tǒng)的(t-1)邊容錯距離，記為D't(G;x，y)，定義為

顯然，

G的(t-1)邊容錯直徑，記為D't(G)，定義為

顯然，

例如，對于無向圈Cn(n≥3)，有D'2(Cn)=n-1.

顯然，對任何t邊連通圖G，有

對邊容錯直徑的研究已經(jīng)有了一些結果，比如，Plesnik［4］就證明了:對任何無向圖G，有D'2(G)≤2d(G)，而且這個上界是最好的，即存在一個2邊連通無向圖G，使得D'2(G)=2d(G).但是，總的來說確定一般圖的邊容錯直徑是相當困難的，還有許多問題期待著被解決.

對于κ(G)和λ(G)，有個重要的結論，是由Whitney［2］得到的，在圖論的研究中經(jīng)常被使用到.

引理1 對于任意圖G，κ(G)≤λ(G)≤δ(G).

引理2 由笛卡爾乘積圖的定義，容易得到它的一些基本性質(zhì).

(a)v(G1×G2)=v(G1)v(G2).

(b)對任何xy∈V(G1×G2)，其中x∈V(G1)且y∈V(G2)(xy)=dG1(x)+dG2(y);特別地，如果G1和G2分別是r1正則和r2正則的，則G1×G2是r1+r2正則的.

(c)對任何y∈V(G2)，G1?G1×{y}?G1×G2;對任何x∈V(G1)，G2?{x}×G2?G1×G2.

(d)由G1×G2的定義，如果P=(x1，v1，v2，…，vm，y1)是G1中一條(x1，y1)路，則對任何b∈V(G2)，(x1b，v1b，v2b，…，vmb，y1b)記為Pb，是G1×G2中從頂點x1b到頂點y1b的路;同樣地，如果W=(x2，u1，u2，…，ul，y2)是G2中一條(x2，y2)路，則對任何a∈V(G1)，(ax2，au1，au2，…，aul，ay2)記為aW，是G1×G2中從頂點ax2到頂點ay2的路;記G1b=G1×，aG2={a}×G2，顯然有Pb?G1b?G1，aW?aG2?G2，故Pb與aW是邊不交.

在提出主要結論之前，引入下面的主要引理，它是由Chiue和Shieh［7］得到的.

引理3 若λ1，λ2，λ分別是G1，G2和G的邊連通度，其中圖G是G1與G2的笛卡爾乘積圖，則有λ≥λ1+λ2.

2 主要結論

笛卡爾乘積圖點容錯直徑和邊容錯直徑的探討并沒有很長時間，再加上點容錯直徑和邊容錯直徑的研究難度很大，所以這方面的結論不是太多.但是，經(jīng)過不斷的努力，仍取得了一些可喜的成果.像關于笛卡爾乘積圖的點容錯直徑，Xu 等［5］證明了:設Gi是ki點連通無向圖，ki≥1，i=1，2，則(G1×G2)≤Dk1(G1)+Dk2(G2)+1;Chiue和Shieh［5］研究了多個圖笛卡爾乘積的點容錯直徑，并得到了一個更廣泛的結果，這里不再詳細地說明.而現(xiàn)在對笛卡爾乘積圖邊容錯直徑的討論似乎還不是太多，似乎是由于刪除邊與刪除點產(chǎn)生的效果有很大不同造成的，但有時兩者的證明思想或許可以相互借鑒.此處嘗試修改和簡化Xu等［5］的方法來對笛卡爾乘積圖的邊容錯直徑進行討論，并得到了一個相關的結論.

根據(jù)笛卡爾乘積圖、邊容錯直徑的部分性質(zhì)和引理1-3，將得到下面的結果.

定理1 設Gi是ti邊連通無向圖，ti≥1，i=1，2，則(G1×G2)≤D't1(G1)+D't2(G2)+1.

證明 令G=G1×G2，t=t1+t2，設 λ1，λ2，λ 分別是圖G1，G2和G的邊連通度，顯然有 λ1≥t1，λ2≥t2，且由引理 1 可得 λ≥λ1+λ2≥t1+t2=t，因此，D't(G)是確定的.令 δi= δ(Gi)，i=1，2，則 δ1≥t1，δ2≥t2.再令F?E(G)，‖F(xiàn)‖=t-1，x和y是G-F中不同的兩個頂點.由于F是邊的集合，顯然V(G-F)=V(G).為了證明定理1，只需要在G-F中構造具有要求長度的xy路S(x，y).

設x=x1x2，y=y1y2，其中x1，y1∈V(G1)，x2，y2∈V(G2)，并設P(x1，y1)是G1中最短(x1，y1)路，Q(x2，y2)是G2中最短(x2，y2)路.

情形1x2=y2.

由于x，y是不同的兩個頂點，故有x1≠y1且x，y∈V(G1x2).

顯然，H1，H2，…，Hδ2均是G的子圖，且兩兩邊不交.因為≥t1，所以H1，H2，…，Hδ2中至少有一個，比如說是H1與F不交(否則‖F(xiàn)‖≥t1+δ2≥t2+t1，這與‖F(xiàn)‖=t-1相矛盾).于是，S:x1x2→x1b1是G-F中長度不超過d(G1)+2的xy路.

綜上所述，D't(G)≤max{(G1)，2+d(G1)}.

情形2x1=y1.

由于x，y是不同的兩個頂點，故有x2≠y2且x，y∈x1G2.

接著使用與情形1中類似的方法，很容易得出，D't(G)≤max{(G2)，2+d(G2)}.

情形3x2≠y2且x1≠y1.

易知，T1，T2，…都是圖G的子圖，且兩兩邊不交.因為≤t2-1，所以其中至少有一個，不妨說是T1與F不交.于是，S:x1x2→x1b1是G-F中長度不超過1+d(G1)+(G2)的xy路.

由前面邊容錯直徑的性質(zhì)，可以得到d(G1)=D'1(G1)≤D'2(G1)≤…≤(G1)與d(G2)=D'1(G2)≤D'2(G2)≤…≤(G2)，利用這兩個不等式可以對(a)(b)和(c)結果進行適當?shù)姆趴s匯總，進而有D't(G1×G2)≤(G1)+(G2)+1.定理1得證.

可以通過考察一些實例來驗證定理1.先看圖G=C4×C4，其中C4是頂點為{1，2，3，4}的無向圈，如圖1.

經(jīng)過計算，發(fā)現(xiàn)取F={(11，12)，(11，14)，(11，41)}(圖 1 中虛線部分)，則D'4(C4×C4)的值就是頂點 11和43在G-F中的距離.在圖1中用黑線部分標示出了頂點11到43的一條最短路，容易看出它的值是5，因此，5=D'4(C4×C4)≤D'2(C4)+D'2(C4)+1=7.

再看圖G=P2×P2=C4，其中P2是長為1的路，如圖2.

任取C4的一條邊，比如說是e，使F={e}(圖2中虛線部分).于是，

圖1 G=C4×C4

圖2 G=P2×P2

這個例子還說明定理1的上界已經(jīng)是最好的了.

［1］徐俊明.圖論及其應用［M］.合肥:中國科技大學出版社，1998

［2］WHITNEY H.Congruent graphs and the connectivity of graphs［J］.American Journal of Mathe-matices，1932(54):150-168

［3］徐俊明.組合網(wǎng)絡理論［M］.北京:科學出版社，2008

［4］PLESNIK J.Note on diametrically critical graphs［J］.In Recent Advances in Graph Theory，Prague:Academia，1975:455-465

［5］XU M，XU J M，HOU X M.Fault diameter of Cartesian product graphs［J］.Information Proces-sing Letters，2005，95(5):245-248

［6］BANIE I，EROVNIK J.The fault-diameter of Cartesian products［J］.Appl Math，2008(40):98-106

［7］CHIUE W S，SHIEH B S.On connectivity of the Cartesian product of two graphs［J］.Applied Math and Computation，1999，102:129-137