ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



ĿɿԵĶʽʱ㷨
׷סˡ
ժҪ硪ORC-IRC-,һǵĸͨſɿ(һض()ÿͨŵĸ)Ķʽʱ㷨.ORC-IRC-,㷨ʱ临ӶȷֱO(E)O(V*E),,V,Eֱʾͱߵ.
ؼʡ,ɿ,㷨,㷨.
ͼšTP302
A Polynomial Time Algorithm for Computing Reliability of 
Two Classes of Networks
KONG Fan-jiaZHANG Xiang-de
Department of Mathematics Northeastern University Shenyang 110006
WANG Guang-xing
Department of Computer Science Northeastern University Shenyang 110006
Abstract In this paper, two classes of directed networksORC-networks and IRC-networks are defined, and a polynomial time algorithm is presented for computing their rooted communication reliability, i.e. the probability that a specified vertex, root vertex, can communicate with all other vertices. The complexity of the algorithm for ORC-networks and IRC-networks is O(E) and O(V*E) respectively, where V and E are the number of vertices and of edges of networks respectively.
Key wordsNetwork, reliability, algorithm, algorithm complexity.
ĸͨſɿָһض()ͨŵĸ.ǼһҪ.ǶԴѾ˹㷺о14.Ľ,һǵĸͨſɿԵĶʽʱ㷨.
1 塢Ǻš
G=(V,E)һͼ,v,wV.wvһߵһ˵,wvһڽ(neighbor).B(v)ʾvڽɵļ.vҽڽ,v2-ڽ.һ(v,w)E,wvһڽ(out-neighbor),vwһڽ(in-neighbor).Vi(v)Vo(v)ֱʾvڽͳڽɵļ.Ei(v)ʾнvıɵļ.vҽһڽ(ڽ),v1-ڽ;vûгڽ,v0-ڽ.sGĸ,ͬһG,ָͬĸ,ĸͨſɿҲͬ.Ϊ˷,ǶGͬsΪһRC-,Gs=(V,E,s)ʾ.,ͬһָͬĸõͬRC-.һֻиRC-ΪƽRC-.sܵÿһ,һɴRC-.һRC-ĸͨſɿR(Gs)ʾ.ǶORC-IRC-.ڶǰ,Ƚ3任.
.2-ڽ任: vGһ2-ڽ,ڽֱu,w.uwֱvһڽһڽ,ô,Gһ(u,w);wuֱvһڽһڽ,ô,Gһ(w,u);ɾv.
.0-ڽ任: vGһ0-ڽ,vһڽ,ô,ɾv.
.1-ڽ任: vGһ1-ڽ,uvڽ,ô,ɾ˵uvı,uvҽԭvбu.
ORC-: һɴRC-,ͨضԷǸ2-ڽ0-ڽ任,õһƽRC-.
IRC-: һɴRC-,ͨضԷǸ2-ڽ㡢0-ڽ1-ڽ任,õһƽRC-.
ƪ,Ķ塢Ǻšοף1,2,5.
2 ʺͿɿԱ
,֤һһĴȦORC-.֤ýǰ,.
1. κһϽĴٺ2-ڽ.
֤:οף3,5,ƪ,.
2. κһȦGٺһ0-ڽ.
֤:ƪ,.
1. κһиĴһиȦ,ǿɴ,һORC-.
֤:GsһиsĿɴﴮ.Gsֻ,ôǸĽһɽ0-ڽ任,ʹGsһƽRC-.GsϽ,1,ܴ2-ڽ.ܴһǸ2-ڽ,2-ڽ任,Ȼٽпܵ0-ڽ任.任GsһƽRC-,ô,Gsһ.ظ,ɽGsƽRC-.ڴиsȦ,2,ܴһ0-ڽ.ΪGsǿɴRC-,s0-ڽ,0-ڽ0-ڽ任,GsܱƽRC-.

Ϊ˼ORC-IRC-ĸͨſɿ,µĿɿԱ(reliability-preserving reduction),.
(1) 0-ڽ:vGsһ0-ڽ,vһڽ,ǳڽ,ڽ.GsɾvGs,ôR(Gs)=R(Gs),隸=1-eiEi(v)qei.
(2) 1-ڽ:vGsһ1-ڽ,uvڽ.ɾ˵ֱuvб,uv,ԭvıuGs.ôR(Gs)=R(Gs),隸=p(u,v).
3 㷨ʱ临
һ㷨,ʶһRC-ǷORC-IRC-.,㷨ͨſɿR(Gs),,һIRC-Ϣ.㷨õĲ2-ڽף1,2,5.
㷨.
: һRC-Gs=(V,E,s)ÿeĿɿpe.
: GsIRC-,R(Gs),GsIRC-Ϣ.
Begin
1.ʹGsǷǿɴ,,Print(GsһɴRC-,R(Gs)=0).
2.f1.0,stackV-s,Vÿ㡰in.
3.{ʶ2-ڽ0-ڽ㲢Ӧ}.
While (stack) do
Begin
(a) stackȡһv,out.
(b) ˳һһؿvı,ֱ¼vڽڽ,ֱvĳڽ0,ͬʱvڽ2{˵vȲ2-ڽ,Ҳ0-},vб߶ѿΪֹ.,ֲ,ͬʱв.
(c) If (No(v)=0ߣB(v)2) then
Begin
.B(v)бǡoutĽǡinstack.
.If (N0(v)=0ߣB(v)=1), then 0-ڽ.
Else {vһ2-ڽ}2-ڽ.
.f=f*.
End.
End.
4.If GsƽRC-,then Print(GsһORC-,R(Gs)ǡf), stop.
5.stackV-s,V-sÿ㡰in.
6.{ʶ2-ڽ,0-ڽ1-ڽ,Ӧ}.
While (stack) do
Begin
(a) stackȡһv,out.
(b) ˳һһؿvı,ֱ¼vڽڽ,ֱvĳڽ0,ͬʱvڽ1,vڽ2{˵vȲ2-ڽ,Ҳ0-ڽ1-ڽ},vıѾΪֹ.,ֲʱ,ͬʱҲв.
(c) If (No(v)=0B(v)=2Ni(v)=1).
Begin
.B(v)бǡoutĽǡin,Ǽstack.
.If (No(v)=0){vһ0-ڽ} then 0-ڽ.
Else if (B(v)=2){vһ2-ڽ} then 2-ڽ.
else {vһ1-ڽ}1-ڽ.
.f=f*.
End.
7.If GsһƽRC- then Print(GsһIRC-,R(Gs)ǡ, f), stop.
Else Print(GsһIRC-硱), stop.
End
㷨ĸ.
2. 㷨ORC-GsIRC-GsĸͨſɿR(Gs)ʱ临ӶȷֱO(E)O(V.E),,V,EֱʾGsĽͱߵ.
֤:֤ϳ,ƪ,ǽ֤һؼʵ,ڵ3,УE+3Vͨstack.ʼV-1stack,ÿִһ2-ڽɾһ,stack.Խ2-ڽ,2Vstack.ÿִһ0-ڽ,E*stack,,E*ǽ0-ڽɾߵ.,ִ0-ڽ,УEstack.ܹУE+3Vͨstack.֤ף2,3,.

߿׷,1963,ʿ,ҪоΪɿ,ݴ.,1937,ڣʿʦ,ҪоΪӦ,ͨ.,1963,ʿ,ڣҪоΪѧͨ.
ͨѶϵ:׷ף 110006,ѧѧϵ
ߵλ׷ £ѧѧϵ110006
ˣѧѧϵ110006

ο
1Page L B, Perry J E. Reliability of directed networks using the factoring theorem. IEEE Transactions on Reliability, 1989,38(5):556562
2Agrawal A, Satyanarayana A. Network reliability analysis using 2-connected digraph reductions. Networks, 1985,15(3):239256
3Politof T, Satyanarayana A. Efficient algorithms for reliability analysis of planar networksa survey. IEEE Transactions on Reliability, 1986,35(3):252258
4Zhao Lian-chang, Kong Fan-jia. A new formula and an algorithm for reliability analysis of network. Microelectronic Reliability, 1997,37(3):511518
5Agrawal A, Satyanarayana A. An O(E) time algorithm for computing the reliability of a class of directed networks. Operations Research, 1984,32(3):493515
1998-03-12ո壩
