关于θ餐嫉谋叩阃络可靠度

王东霞

【摘要】本文对边点网络可靠度计算的展开定理做了进一步推广，并得到了θ-图两个2度点之间的可靠度公式，在网络设计和优化方面具有一定指导意义

【关键词】网络可靠性；边点网络；展开定理

引 言

在网络可靠性研究中，人们大多研究的是点可靠边不可靠的可靠性问题，一些重要的理论都有系统的描述[12]；近年来在边可靠点不可靠网络可靠性研究方面，Goldschmidt[3]等人取得了很大进步，而对于边点都不可靠的可靠性问题的研究非常少[4]，而实际上，把某些工程领域的数字系统或其他系统抽象为数学模型，边点都不可靠更符合实际情况，更具有一般性，未定义的图论术语与记号见文献[5]本文把网络可靠度的展开定理[4]进一步推广，并利用推广定理计算了θ-图的可靠度多项式，在网络设计和优化方面具有一定指导意义.

一、关于边、点及边点网络可靠度

1.点可靠边不可靠

所谓点可靠边不可靠是指网络G的点总是正常工作，而其边有（正常）工作与失效两种状态，而且各边工作彼此在统计上是相互独立的且具有相同的概率p（0≤p≤1），具有n点m边的网络G的全终端可靠度R（G，p）表示G中至少存在一个工作的连通生成子图的概率，即网络上任意两点能够进行通讯的概率.它可写成关于p 的多项式——可靠度多项式R（G，p）=∑mr=n-1Nr（G）prqn-r，其中q=1-p.Nr（G）表示G中具有r条边的连通生成子图的个数.R（G，p）称为网络的全终端可靠度.

展开定理1[4]：对一条边展开

R（G）=pf1（G）+（1-p）f0（G）

其中：p为网络第i边连通的概率，f1（G）为第i个边连通时网络的可靠度，f0（G）为第i个边不通时网络的可靠度.

对于点可靠边不可靠的网络可靠度计算还可以用分解定理，它和展开定理形式相同，但是更具体，利于应用.

分解定理：令G是一个无向图，G可能有重边但无环.e=uv∈E（G），则R（G）=peR（G·e）+qeR（G-e），其中pe及qe分别为边e工作与失效概率；g-e是将G的边l去掉后形成的G的子图；G·e是将边e两端点u与v重合成一个新点w而形成的新图.

2.点不可靠边可靠

所谓点不可靠边可靠是指在一个图G中其边发生故障的概率为0，其点却以1-p的概率相互独立的发生故障，则图G连通的概率R（G，p）=∑nr=1Sr（G）pr（1-p）n-r，其中：Sr（G）是图G中含有r个节点的连通诱导子图的个数

展开定理2[4]：对一个顶点展开

R（G，P）=pf1（G）+（1-p）f0（G）

其中：p为网络第j个点通的概率，f1（G）为第j个点通时网络的可靠度，f0（G）为第j个点不通时网络的可靠度

3.边点都不可靠

所谓边点都不可靠是指在一个图G中其边相互独立发生故障的概率为p1，其点以p2的概率相互独立的发生故障，则图G的可靠度为：

R（G，P1，P2）=∑nk=1∑rmr=oAkmpk1p2m（1-p1）n-k（1-p2）r-m

其中 Akm为特征值，所求网络连通时Akm=1，所求网络不连通时Akm=0.

展开定理3[4]：

对一条边一个顶点展开

R（G）=AP1+BP2+CP1P2+D

其中： A=f10-f00，B=f01-f00，C=f11+f00-f10-f01；

D=f00

f10为第i条边通，第j个节点不通时网络的可靠度；

f01为第i条边不通，第j个节点通时网络的可靠度；

f11为第i条边，第j个节点都通时网络的可靠度；

f00为第i条边，第j个节点都不通时网络的可靠度.

展开定理3还可以进一步推广：

展开定理3的推广：其中的第i条边可以推广为包含有m个二度点的链，此时，这条链连通的概率为pm-11pm-22（不包含链的端点）用这个概率代替展开定理3中的p1便可以得到一些较复杂图的可靠度计算公式R（G）=APm-11pm-22+BP2+CPm-11Pm-12+D.其中A、B、C、D所代表的含义和定理3中类似，只需把第i条边换成第i条链即可.

二、θ-图的边点网络可靠度

θ-图是所有n点 n+1 边图中点可靠边不可靠的一致最优可靠图，下面就应用展开定理3的推广定理来计算θ -图上两个二度点的连通概率.

设C、D都为3度点A、B是这两个3度点之间不在同一条边上的任意两个2度点，a、b、c、d、e、f、e分别为AD、AC、CB、BD、CD之间2度点的个数，现在就来计算AB连通的概率，根据推广定理对链a和顶点D分解：分别作出f10，f01，f11，f00对应的网络如

f10=P（AbCcB）=P（b+c+3）2P（b+c+2）1

f01=P（AbCcB+AbCeDdB）=P（AbCcB）+P（AbCeDdB）-P（AbCeDdBc）

=P（b+c+3）2P（b+c+2）1+P（b+e+d+4）2P（b+e+d+3）1-P（b+c+d+e+4）2P（b+c+d+e+4）1

f00=P（AbCcB）=P（b+c+3）2P（b+c+2）1

f11=P（AdD+AbCcD+AeCcD）=P（AdD）+P（AbCcD）+P（AeCcD）

-P（AbCcDd）-P（AdDcCe）-P（AbeCcD）+P（ACDbced）

=P（d+2）2P（d+1）1+P（b+c+2）2P（b+c+1）1+P（c+e+2）2P（c+e+1）1-P（b+c+d+3）2P（b+c+d+3）1-P（c+d+e+3）2P（c+d+e+3）1-P（b+c+e+3）2P（b+c+e+3）1+P（b+c+d+e+3）2P（b+c+d+e+4）1

代入可靠度公式又注意到a+b+c+d+e+4=n，m=a+2因此

R（G）=APm-11pm-22+BP2+CPm-11Pm-12+D

=（f01-f00）p2+（f11+f00-f10-f01）Pa+11Pa+12+f00

=P（b+d+e+5）2P（b+d+e+3）1+P（a+d+3）2P（a+d+2）1+P（a+b+c+3）2P（a+b+c+3）1+pa+c+e+32pa+c+e+21+pn2pn+11+pn+12pn+11+P（b+c+3）2P（b+c+2）1-P（n+1-a）2P（n-a）1-P（n-e）2P（n-e）1-pn-b2pn-b1+pn-d2pn-d1-P（a+b+c+4）2P（a+b+c+4）1-P（n+1-c）2P（n-c）1

至此得到了θ-圖的边点可靠度多项式，它在网络设计和优化方面具有一定指导意义.

【参考文献】

[1]COLBOURNCJ.The Combinations of Network Reliability[M].Oxford：Oxford University Press，1987.

[2]SHIER D R.Network Reliability and Algebraic Structures[M].Oxford：Clarendon Press，1991.

[3]GOLDSCHMIDTO，JAILLETP，LAOSOTA R.On reliability of graphs with node failures[J].Networks，1994，24（4）：251-259.

[4]赵沁平，王化奎.关于“边点网络”的可靠度.太原理工大学学报[J]1980，03：47-55.

[5]Bondy J A，Murty USR.Graph Theory with Applications[M].London MacMillan Press，1976.