鄒婷婷，曾雪倩，李向軍

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

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

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

1 預(yù)備知識

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

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

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

性質(zhì)1[16]當(dāng)2≤k

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

2 主要結(jié)果

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

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

證明不失一般性，在H1中取一個(h+1)-團(tuán)(記為X)，F(xiàn)表示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，對于任意頂點(diǎn)u∈Hj，由于Hj是一個(n-1)-團(tuán)，所以δY(u)≥δHj(u)=n-2≥h.對于任意頂點(diǎn)u∈H1-X,u有(n-2)個外鄰點(diǎn)，從而有δY(u)≥n-2≥h，所以δ(Y)≥h.故F是一個h-邊割，λh(An,2)≤|F|=(h+1)(2n-h-4).引理得證.

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

證明根據(jù)引理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有對稱性，不妨假設(shè)|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條相互獨(dú)立的邊，故|EC|≥bc(n-2).

用EI表示∪j3∈J0Xj3與∪j3∈J0Yj3之間所有的邊，對于j3∈J0,由于Hj3同構(gòu)于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).

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

下面考慮a

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

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

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

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

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

3 結(jié)語

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