有向網(wǎng)絡(luò)s可靠性的線性時間算法

有向網(wǎng)絡(luò)s可靠性的線性時間算法

1有向網(wǎng)絡(luò)的st可靠性隨著計算機網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)規(guī)模不斷擴大，網(wǎng)絡(luò)的可靠性日益重要。網(wǎng)絡(luò)可靠性是計算機網(wǎng)絡(luò)和通信網(wǎng)絡(luò)設(shè)計和運營的重要參數(shù)，因此引起了人們的廣泛注意。在可靠性問題上，包括st可靠性、k終端可靠性和全終端可靠性?，F(xiàn)在，已經(jīng)發(fā)表了許多關(guān)于它的計算的研究文獻(xiàn)，但對于具有方向的網(wǎng)絡(luò)，只有通過線性時間計算非圈網(wǎng)絡(luò)的根通信的可靠性，st可靠性是非常困難的。因此，在搜索無限制網(wǎng)絡(luò)時，需要線性時間來計算可靠性。因此，g=（v，e）是一個可能的網(wǎng)絡(luò)損壞邊緣網(wǎng)絡(luò)。s和t是指g的兩個特定節(jié)點，即g的源點和銷節(jié)點。邊界效率是眾所周知的。g的st可靠性是指從源點s到匯點t通常運行路徑的概率，g的st可靠性是指從源點s到匯點t的通常可靠性問題，然而，對于具有導(dǎo)向網(wǎng)絡(luò)的特殊類型的st可靠性，存在線性時間算法。對于面向無圈網(wǎng)絡(luò)（ad-net）的st可靠性，也非常簡單。因此，我們希望在盡可能廣泛的網(wǎng)絡(luò)中找到一家網(wǎng)絡(luò)，并在線性時間內(nèi)計算st可靠性。2wst網(wǎng)絡(luò)的結(jié)構(gòu)平凡AD-網(wǎng)絡(luò):僅含一結(jié)點的網(wǎng)絡(luò).s可達(dá)AD-網(wǎng)絡(luò):s點能到達(dá)每一個其它結(jié)點的AD-網(wǎng)絡(luò).2(1)-鄰域點:恰有2(1)個鄰域點的結(jié)點.子圖G1的入(出)鄰域:一個結(jié)點w屬于子圖G1的入(出)鄰域如果存在一條從w(G1中結(jié)點v)到G1中結(jié)點v(w)的邊,所有這樣的結(jié)點的集合稱為子圖G1的入(出)鄰域,分別記為Ni(G1),No(G1).子圖G1鄰域:G1的入鄰域和出鄰域的并,記為N(G1).圖G的惠斯通橋:若圖G中有兩相鄰結(jié)點{x,y}的鄰域N(x,y)={u,v},則稱{x,y,u,v}四個結(jié)點構(gòu)成的子圖為圖G的一惠斯通橋,記為W(u,v,x,y),u,v為W(u,v,x,y)的端點.子圖G1的入(出)鏈鄰域:一個結(jié)點w屬于子圖G1的入(出)鏈鄰域如果存在一條從w(G1中結(jié)點v)到G1中結(jié)點v(w)的路,且N(w)≠2,鏈上的結(jié)點除v,w外均為2-鄰域點,所有這樣的結(jié)點的集合稱為子圖G1的入(出)鏈鄰域,分別記為Pi(G1),Po(G1);G1的鏈鄰域P(G1)=Pi(G1)∪Po(G1).圖G的源橋:若圖G中有一鏈x→y的鏈鄰域P(x,y)={u,v},且s在某一路上,t一定不是該子圖除u,v外的結(jié)點,則稱{x,y,u,v}四個結(jié)點及路上的結(jié)點構(gòu)成的子圖為圖G的源橋,記為SW(u,v,x,y),u,v為SW(u,v,x,y)的端點.融合邊e:刪除邊e,其端點為w和v,刪除結(jié)點w,每條與w關(guān)聯(lián)的邊現(xiàn)與v關(guān)聯(lián),記為G*e.(w,v):一條從w到v的邊.pi(qi):邊i的可靠性(不可靠性).Ωi,Ω:可靠性保護(hù)縮減的乘因子.G-e(G-v):在G中刪除邊e(結(jié)點v).BSP網(wǎng)絡(luò):若一有向網(wǎng)絡(luò)對應(yīng)的基礎(chǔ)無向圖是串并聯(lián)網(wǎng)絡(luò).WST網(wǎng)絡(luò):WST網(wǎng)絡(luò)是遞歸定義的.①無圈網(wǎng)絡(luò)且BSP網(wǎng)絡(luò)是WST網(wǎng)絡(luò);②(u,v)是一WST網(wǎng)絡(luò)的任一有向邊,用W(u,v)替換之,得到的新網(wǎng)絡(luò)仍是WST網(wǎng)絡(luò).假設(shè)①邊和網(wǎng)絡(luò)或是運行的,或是失效的.每一條邊的失效的概率是已知的,而且是S-獨立的.②由有向圖的ST可靠性的定義可知:若有一結(jié)點不可靠,如圖1所示.若v∈{s,t},則Rst(G)=pvRst(G1)在G1中v是不失效的結(jié)點.若v?{s,t},則有Rst(G)=Rst(G1),在G1中Ni(u1)為G中的Ni(u);No(u2)為G中的No(u);且有p(u1,u2)=pu.因此假設(shè)G=(V,E)中結(jié)點不失效是合理的.③假定G=(V,E)中每一結(jié)點是s-可達(dá)的,若有一結(jié)點不可達(dá),則刪除該結(jié)點不影響G的ST可靠性,因此該假設(shè)也是合理的.3增加一條邊u,w的可靠性對于BSP網(wǎng)絡(luò)的ST可靠性問題可以反復(fù)應(yīng)用2-鄰點縮減,并聯(lián)縮減和源-三角形縮減將該網(wǎng)絡(luò)縮減為平凡網(wǎng)絡(luò),即只含一個結(jié)點的網(wǎng)絡(luò).對于WST網(wǎng)絡(luò)我們將應(yīng)用以上的縮減和兩類新的可靠性保護(hù)縮減,并證明對該類網(wǎng)絡(luò)可以線性時間得到其ST可靠性.下面介紹我們算法所使用的縮減.并聯(lián)縮減:讓e1=(u,v),e2=(u,v)是G的兩條并聯(lián)邊,于是用e3=(u,v)替換e1,e2得到網(wǎng)絡(luò)G1,使得pe3=1-qe1qe2,Ω=1(圖2).s-鄰域點縮減:若e=(s,v)是從源點s出來的唯一的一條邊,那么融合結(jié)點v進(jìn)入源點s得到G1,且Ω=pe(圖3).t-鄰域點縮減:若e=(v,t),是進(jìn)入?yún)R點t的唯一的一條邊,那么融合結(jié)點v進(jìn)入源點t得到G1,且Ω=pe(圖4).2-鄰域點縮減:若v是G的2-鄰域點,它的兩個鄰域點分別是u和w,且v≠s,p(u,v),p(v,w),p(v,u),p(w,v)分別是(u,v),(v,w),(v,u),(w,v)的可靠性(若某邊不存在,則該邊的可靠性為0)p(u,w)=p(u,v)p(v,w),p(w,u)=p(v,u)p(w,v).于是G被生成通過刪除結(jié)點v,若p(u,w)≠0,那么增加一條邊(u,w),其可靠性為p(u,w);若p(w,u)≠0,那么增加一條邊(w,u),其可靠性為p(w,u),且Ω=1(圖5).源-三角形縮減:若s是G的2-鄰域點,它的兩個鄰域點分別是u和v,可以進(jìn)行如圖6的可靠性保護(hù)縮減.px=A/B,Py=A/C,Ω=BC/A,A=pa(pb+qbpd)+qapbpc,B=pb+paqbpd,C=pa+qapbpc,以上幾種縮減稱為簡單縮減.定理1.惠斯通橋縮減:在AD-網(wǎng)絡(luò)中有惠斯通橋W(u,v,x,y),{x,y}∩{s,t}=?,則該橋可以用一條邊e替換得到G1,且pe=papb+papbˉˉˉˉˉˉ(pcpdˉˉˉˉˉˉpe+pcpd)(圖7).證明.在AD-網(wǎng)絡(luò)中由于無圈,因而惠斯通橋只有圖7一種同構(gòu)形式.所以有R(G)=P(∪Pi)將Pi分為兩類,{x,y}不在其上,記為Pst,{x,y}至少有一個在上面,分別記為PsuxPvt,PsuxyPvt,PsuyPvt.R(G)=P(∪Pst)+P(PsuxPvt)+P(PsuxyPvt)+P(PsuyPvt)=P(∪Pst)+P(∪Psu(ab+cd+aed)∪Pvt)=P(∪Pst)+P(∪Psu(u,v)∪Pvt)=R(G1)?P(u,v)=papb+pcpd+papepd=papb+papbˉˉˉˉˉˉpcpd+papbˉˉˉˉˉˉpcpdˉˉˉˉˉˉpapepd=papb+papbˉˉˉˉˉˉpcpd+(paˉˉˉ+pbˉˉˉ)(pcˉˉˉ+pdˉˉˉ)papepd=papb+papbˉˉˉˉˉˉpcpd+papbˉˉˉˉˉˉpcpdˉˉˉˉˉˉpe=papb+papbˉˉˉˉˉˉ(pcpd+pcpdˉˉˉˉˉˉpe)定理得證.證畢.定理2.若源橋SW(u,v,x,y)不能進(jìn)行簡單縮減,則它一定只有如圖8—10所示的三種同構(gòu)形式或是其中一種的子圖.且其可靠性保護(hù)縮減由表1給出.由于有向網(wǎng)絡(luò)對源點的出邊因子定理是成立的,分別計算圖8—10所示的形式.由于方法類似,我們只給出圖8的計算過程,圖9和圖10只給出結(jié)果.Pc1=pc+qc(1-qbqf)pg,G1=G-y,R(G)=ΩR(G1),papc1+qa(pcpc2+qcpbpdpg)=Ωpxpy=A,paqc1+qaqcpbpdqg=Ωpxqy=B,qa(pcqc2+qcpbqdpg)=Ωqxpy=C,Pc1=pc+qc(1-qbqf)pg,pc2=pd(1-qbqe),得px=A/(A+C),py=A/(A+B),Ω=(A+B)(A+C)/A.類似方法可得圖9—10的源橋縮減.定理3.源橋縮減:若有向圖G有源橋,則R(G)=ΩR(G1),且px=A/(A+C),py=A/(A+B),Ω=(A+B)(A+C)/A.A,B,C的值見表1.這里第一類5個縮減已經(jīng)在不同的文章中給出(敘述略有不同,但本質(zhì)一樣),而后兩類縮減是新的,在新的算法中起著至關(guān)重要的作用.下面我們介紹WST網(wǎng)絡(luò)的幾個性質(zhì).引理1.2-連通圖G,若無2度結(jié)點,且無并聯(lián)邊,則該圖一定有同胚惠橋的子圖.定理4.圖DG是有向WST網(wǎng)絡(luò)的充要條件是其對應(yīng)的基礎(chǔ)子圖G無同胚四棱錐和三棱柱的子圖.證明.我們不妨假定圖G是2-連通的,否則有割點,設(shè)為a,G=G1∪G2,若s,t同時在a的一側(cè),設(shè){s,t}?G1,則Rst(G)=Rst(G1),否則設(shè)s∈G1,t∈G2,Rst(G)=Rsa(G1)Rat(G2).(1)必要條件.我們可以對n=|V(DG)|做歸納法.當(dāng)n=1時,DG的基礎(chǔ)子圖為K2,顯然G無同胚四棱錐和三棱柱的子圖.歸納假設(shè)當(dāng)n<k時,G無同胚四棱錐和三棱柱的子圖.當(dāng)n=k時,①當(dāng)G有結(jié)點v,deg(v)=1,刪除該結(jié)點,G1=G-v,|E(G1)|=k-1<k.②當(dāng)G有并聯(lián)邊e1,e2,刪除e1,G1=G-e1,|E(G1)|=k-1<k.③當(dāng)G有串聯(lián)邊e1和e2,用e3替換e1,G1=G-e1-e2+e3,|E(G1)|=k-1<k.對于上述的三種情況根據(jù)WST網(wǎng)絡(luò)的定義可知G1是WST網(wǎng)絡(luò),因而G1無同胚四棱錐和三棱柱的子圖,所以G也不可能有無同胚四棱錐和三棱柱的子圖.④當(dāng)G是串并聯(lián)網(wǎng)絡(luò),則G無同胚三棱錐的子圖,所以G也無同胚四棱錐和三棱柱的子圖.⑤以上幾種情況均不成立,根據(jù)WST網(wǎng)絡(luò)的定義,G一定有W(u,v,x,y),令G1=G-W(u,v,x,y)+(u,v),G1是WST網(wǎng)絡(luò),G1無同胚四棱錐和三棱柱的子圖,u,v,x,y不可能構(gòu)成四棱錐和三棱柱上的結(jié)點,因而G也無同胚四棱錐和三棱柱的子圖.因此WST網(wǎng)絡(luò)無同胚四棱錐和三棱柱的子圖.(2)充分條件.我們也可以對n=|V(DG)|做歸納法.當(dāng)n=1時,DG的基礎(chǔ)子圖為K2,顯然DG是WST網(wǎng)絡(luò).歸納假設(shè)當(dāng)n<k時,DG是WST網(wǎng)絡(luò).當(dāng)n=k時,若①—④成立,同上操作,由歸納可知G1是WST網(wǎng)絡(luò),由WST網(wǎng)絡(luò)的定義知G也是WST網(wǎng)絡(luò).若G有惠斯通橋W(u,v,x,y),令G1=G-W(u,v,x,y)+(u,v),G無同胚四棱錐和三棱柱的子圖,G1無同胚四棱錐和三棱柱的子圖.G1是WST網(wǎng)絡(luò),因而根據(jù)WST網(wǎng)絡(luò)的定義G也是WST網(wǎng)絡(luò).這時該圖一定是非BSP網(wǎng)絡(luò),其基礎(chǔ)子圖有同胚K4的子圖,如圖12所示,4個頂點分別為1,2,3,4;6條路為Pij,1<i,j<3,按結(jié)點將G分為6個集合,Gij為不通過另外2個結(jié)點與i,j連通的結(jié)點構(gòu)成的子圖,Gij∩Gik=i,除i外Gij的結(jié)點不可能與Gik的除i外結(jié)點相鄰,否則一定有子圖同胚四棱錐或三棱柱.這樣一來我們可以把G分為6部分,G=Gij∪Gik,若Gij中有5個為K2,則G有惠橋;否則設(shè)G12不為K2,則至少有一結(jié)點a,根據(jù)引理1可知,G12有同胚惠橋W(5,6,7,8)的子圖,這樣我們得到一個新的同胚K4的子圖,可以把G重新分為6個子圖,G56?∪Gij,ij≠12,G56結(jié)點增多,我們可以不斷這樣做下去,總可以使其中的5部分為K2,因此G有惠橋設(shè)為W(u,v,x,y),DG-W(u,v,x,y)+(u,v)是WST網(wǎng)絡(luò),根據(jù)WST網(wǎng)絡(luò)的定義可知DG也是WST網(wǎng)絡(luò).證畢.推論1.(1)DG網(wǎng)絡(luò)是WST,網(wǎng)絡(luò)則其子圖也是WST網(wǎng)絡(luò).(2)WST網(wǎng)絡(luò)是平面圖.(3)WST網(wǎng)絡(luò)經(jīng)過如上的縮減仍為WST網(wǎng)絡(luò).定理5.DG為WST網(wǎng)絡(luò),且不能進(jìn)行簡單縮減,則DG至少有2個惠橋或為K2.證明.DG非平凡,根據(jù)定義知DG有惠橋,設(shè)為W(u,v,x,y),類似定理1的證明知DG1=DG-W(u,v,x,y)或有惠橋或為K2,當(dāng)DG1=K2,則DG有惠橋W(x,y,u,v).證畢.推論2.若非平凡的WST網(wǎng)絡(luò),若不能進(jìn)行簡單縮減且無惠斯通橋和源橋,則為同胚K4圖.4惠橋、源橋和同胚k4的算法計算輸入:有向網(wǎng)絡(luò)DG,源點s,匯點t,各邊的正常工作概率pei,ei∈E.輸出:Rst(G),或給出非WST網(wǎng)絡(luò)的信息.1.R=1,對DG進(jìn)行簡單縮減,R=R×Ω.2.對DG進(jìn)行惠橋搜索,只需檢查所有相鄰的3-鄰域結(jié)點,若找到一個惠橋,則2.1.是惠斯通橋,進(jìn)行惠斯通橋縮減,R=R×Ω,對橋的兩端點進(jìn)行簡單縮減,返回2.2.2.是源橋,進(jìn)行源橋縮減,R=R×Ω,對橋的兩端點進(jìn)行簡單縮減,返回2.3.3.1.DG=K2,則輸出R.3.2.DG同胚K4,計算其可靠性,輸出R.3.3.DG為非WST網(wǎng)絡(luò).定理6.WST網(wǎng)絡(luò)的可靠性的算法復(fù)雜性是O(|E|2).證明.第1步我們只需檢