排列圖的限制邊連通度

鄒婷婷，曾雪倩，李向軍

(長江大學 信息與數學學院，湖北 荊州 434023)

在大規模多元信息處理系統中，元件故障不可避免，當故障發生時網絡對某些條件性質的保持能力就是它的容錯性能.在設計大規模網絡時，高性能、低成本是最終目標.在選擇互連網絡的拓撲結構時，處理器之間的有效通信是衡量系統性能的一個重要標準，當處理器數目逐漸增多時，其發生故障的可能性也隨之增加，不同處理器之間信息傳遞過程中的容錯性便成為一個非常關鍵的問題，為此有必要考慮網絡的容錯性和可靠性.點連通度(記作κ(G))是使得G-T不連通的最小頂點子集T的基數；邊連通度(記作λ(G))的定義類似，它是使得G-F不連通的最小邊子集F的基數.但連通度假設任意頂點和任意邊可以同時發生故障，在實際應用中并不能很好地反映網絡的彈性，Harary針對這一弱點，引入了條件連通度的概念，對剩余的網絡提出了一些附加要求[1].此后，Latifi等[2]在一定意義上推廣了這一概念，通過限制每個頂點至少有h個無故障鄰點，提出了h-限制連通度.在實際應用中，這些廣義度量可以更準確地估計互連網絡的容錯性.

用無向圖G=(V;E)表示互連網絡的拓撲結構，圖G的頂點V(G)代表系統中的元件，圖G的邊E(G)代表元件之間的物理連線[3].對于u∈V,u的度是與u關聯的邊數，記作d(u)，δ(G)表示圖G的最小度.假設G為連通圖，T是V(G)的子集，若G-T不連通且最小度至少為h，即δ(G-T)≥h，稱T是圖G的h-點割，h-限制點連通度(記作κh(G))是最小h-點割的基數.對于邊故障的網絡容錯性刻畫也有類似度量，F是E(G)的子集，若G-F不連通，且δ(G-F)≥h，稱F是圖G的h-邊割，h-限制邊連通度(記作λh(G))是最小h-邊割的基數.顯然有κ0=κ,λ0=λ.對有向圖的點割研究也有不少學者關注[4-6]，本文的主要研究對象是無向排列圖.在排列圖的容錯性研究方面，國內外學者對其點故障關注較多，Zhou等[7]、林麗美等[8]、Cheng等[9-10]學者在其限制連通度方面得到了部分重要結果；Wang等[11-12]、Lin等[13]、Lei等[14]、Xu等[15]等學者在子結構容錯方面做了很好的工作.目前對排列網絡邊故障情況的分析和探討還較少，而現實網絡中連線故障是確實存在的，本文利用圖結構分析方法對排列圖An,2的邊故障容錯能力進行探索，當h≤3時確定其限制邊連通度λh(An,2)，該結果可為進一步分析排列圖的邊故障容錯能力提供借鑒.

1 預備知識

定義1[16]令n,k為兩個整數，且1≤k

圖1 排列圖A5,1和A4,2Fig.1 The arrangement graphs A5,1 and A4,2

用Hi表示An,k一個頂點子集，它是第j(1≤j≤k)個位置元素pj為i(1≤i≤n)的排列.對頂點v∈Hi，v在Hi中的鄰點稱為內鄰點，v在An,k-Hi中的鄰點稱為外鄰點.

性質1[16]當2≤k

性質3[16]對于Hi中的j個頂點，它們有j(n-k)個不相交的外鄰點.

2 主要結果

主要考慮排列圖An,2的h-限制邊連通度.

引理1 當0≤h≤n-2時，λh(An,2)≤(h+1)(2n-h-4).

證明不失一般性，在H1中取一個(h+1)-團(記為X)，F表示X與N(X)之間所有的邊.由于An,2是2(n-2)-正則的，有|F|=2(n-2)(h+1)-h(h+1)=(h+1)(2n-h-4).

以下證明F是一個h-邊割，令Y=G-X，證明δ(Y)≥h即可.如果j≠1，對于任意頂點u∈Hj，由于Hj是一個(n-1)-團，所以δY(u)≥δHj(u)=n-2≥h.對于任意頂點u∈H1-X,u有(n-2)個外鄰點，從而有δY(u)≥n-2≥h，所以δ(Y)≥h.故F是一個h-邊割，λh(An,2)≤|F|=(h+1)(2n-h-4).引理得證.

定理1 當h∈{1,2,3}，n≥h+2時，λh(An,2)=(h+1)(2n-h-4).

證明根據引理1，只需證明λh(An,2)≥(h+1)(2n-h-4).

令F是An,2的最小h-邊割，只需證明|F|≥(h+1)(2n-h-4).

假定X是An,2-F中一個連通分支，Y=An,k-X，令Xi=X∩Hi,Yi=Y∩Hi.

令JX={i∈[n]:Xi≠?},JY={i∈[n]:Yi≠?},J0=JX∩JY；考慮這幾個集合大小，令a=|J0|,b=|JX-J0|,c=|JY-J0|，則a+b+c=n.因為X與Y有對稱性，不妨假設|JX|≤|JY|.由于Hi表示第j(1≤j≤2)個位置元素pj為i(1≤i≤n)的排列，可以選擇某個j(1≤j≤2)使得|JX|盡可能大.

用EC表示∪j1∈JX-J0Hj1與∪j2∈JY-J0Hj2之間所有的邊，對于j1∈JX-J0和j2∈JY-J0,Hj1與Hj2之間有n-2條相互獨立的邊，故|EC|≥bc(n-2).

用EI表示∪j3∈J0Xj3與∪j3∈J0Yj3之間所有的邊，對于j3∈J0,由于Hj3同構于Kn-1，故|EI|≥a(n-2).由于F是邊割，故EI?F.注意到EC?F，則有|F|≥|EC|+|EI|≥bc(n-2)+a(n-2)≥(a+bc)(n-2).

如果bc≠0，則有(a+bc)(n-2)≥(n-1)(n-2)，從而|F|≥(n-1)(n-2)≥(h+1)(2n-h-4).

下面假設bc=0，由|JX|≤|JY|有b=0，從而|JX|=|J0|=a.

下面考慮a

考慮函數f(a)=a(2n-3-a),則|F|≥f(a).易知f(a)在區間[1,n-2]單調增加，且f(n-1)=f(n-2).

h=1時，a≥2，根據f(a)在[1,n-2]單調性，有|F|≥f(a)≥f(2)=4n-10.

h=2時，如果a≥3，由f(a)單調性，可知|F|≥f(a)≥f(3)=6n-18.

h=3時，如果a≥4，由f(a)單調性可知|F|≥f(a)≥f(4)=8n-28.

所以h=1，2，3時都有λh(An,2)≥(h+1)(2n-h-4)，定理得證.

3 結語

研究了排列圖An,2的邊故障容錯能力，對n≥3確定λ1(An,2)=4n-10，對n≥4確定λ2(An,2)=6n-18，對n≥5確定λ3(An,2)=8n-28.當h≥4時確定λh(An,2)，以及對k≤n-2，h≤n-k確定λh(An,k)是值得進一步研究的問題.