王東霞

【摘要】本文對(duì)邊點(diǎn)網(wǎng)絡(luò)可靠度計(jì)算的展開(kāi)定理做了進(jìn)一步推廣，并得到了θ-圖兩個(gè)2度點(diǎn)之間的可靠度公式，在網(wǎng)絡(luò)設(shè)計(jì)和優(yōu)化方面具有一定指導(dǎo)意義

【關(guān)鍵詞】網(wǎng)絡(luò)可靠性；邊點(diǎn)網(wǎng)絡(luò)；展開(kāi)定理

引 言

在網(wǎng)絡(luò)可靠性研究中，人們大多研究的是點(diǎn)可靠邊不可靠的可靠性問(wèn)題，一些重要的理論都有系統(tǒng)的描述[12]；近年來(lái)在邊可靠點(diǎn)不可靠網(wǎng)絡(luò)可靠性研究方面，Goldschmidt[3]等人取得了很大進(jìn)步，而對(duì)于邊點(diǎn)都不可靠的可靠性問(wèn)題的研究非常少[4]，而實(shí)際上，把某些工程領(lǐng)域的數(shù)字系統(tǒng)或其他系統(tǒng)抽象為數(shù)學(xué)模型，邊點(diǎn)都不可靠更符合實(shí)際情況，更具有一般性，未定義的圖論術(shù)語(yǔ)與記號(hào)見(jiàn)文獻(xiàn)[5]本文把網(wǎng)絡(luò)可靠度的展開(kāi)定理[4]進(jìn)一步推廣，并利用推廣定理計(jì)算了θ-圖的可靠度多項(xiàng)式，在網(wǎng)絡(luò)設(shè)計(jì)和優(yōu)化方面具有一定指導(dǎo)意義.

一、關(guān)于邊、點(diǎn)及邊點(diǎn)網(wǎng)絡(luò)可靠度

1.點(diǎn)可靠邊不可靠

所謂點(diǎn)可靠邊不可靠是指網(wǎng)絡(luò)G的點(diǎn)總是正常工作，而其邊有（正常）工作與失效兩種狀態(tài)，而且各邊工作彼此在統(tǒng)計(jì)上是相互獨(dú)立的且具有相同的概率p（0≤p≤1），具有n點(diǎn)m邊的網(wǎng)絡(luò)G的全終端可靠度R（G，p）表示G中至少存在一個(gè)工作的連通生成子圖的概率，即網(wǎng)絡(luò)上任意兩點(diǎn)能夠進(jìn)行通訊的概率.它可寫(xiě)成關(guān)于p 的多項(xiàng)式——可靠度多項(xiàng)式R（G，p）=∑mr=n-1Nr（G）prqn-r，其中q=1-p.Nr（G）表示G中具有r條邊的連通生成子圖的個(gè)數(shù).R（G，p）稱為網(wǎng)絡(luò)的全終端可靠度.

展開(kāi)定理1[4]：對(duì)一條邊展開(kāi)

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

其中：p為網(wǎng)絡(luò)第i邊連通的概率，f1（G）為第i個(gè)邊連通時(shí)網(wǎng)絡(luò)的可靠度，f0（G）為第i個(gè)邊不通時(shí)網(wǎng)絡(luò)的可靠度.

對(duì)于點(diǎn)可靠邊不可靠的網(wǎng)絡(luò)可靠度計(jì)算還可以用分解定理，它和展開(kāi)定理形式相同，但是更具體，利于應(yīng)用.

分解定理：令G是一個(gè)無(wú)向圖，G可能有重邊但無(wú)環(huán).e=uv∈E（G），則R（G）=peR（G·e）+qeR（G-e），其中pe及qe分別為邊e工作與失效概率；g-e是將G的邊l去掉后形成的G的子圖；G·e是將邊e兩端點(diǎn)u與v重合成一個(gè)新點(diǎn)w而形成的新圖.

2.點(diǎn)不可靠邊可靠

所謂點(diǎn)不可靠邊可靠是指在一個(gè)圖G中其邊發(fā)生故障的概率為0，其點(diǎn)卻以1-p的概率相互獨(dú)立的發(fā)生故障，則圖G連通的概率R（G，p）=∑nr=1Sr（G）pr（1-p）n-r，其中：Sr（G）是圖G中含有r個(gè)節(jié)點(diǎn)的連通誘導(dǎo)子圖的個(gè)數(shù)

展開(kāi)定理2[4]：對(duì)一個(gè)頂點(diǎn)展開(kāi)

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

其中：p為網(wǎng)絡(luò)第j個(gè)點(diǎn)通的概率，f1（G）為第j個(gè)點(diǎn)通時(shí)網(wǎng)絡(luò)的可靠度，f0（G）為第j個(gè)點(diǎn)不通時(shí)網(wǎng)絡(luò)的可靠度

3.邊點(diǎn)都不可靠

所謂邊點(diǎn)都不可靠是指在一個(gè)圖G中其邊相互獨(dú)立發(fā)生故障的概率為p1，其點(diǎn)以p2的概率相互獨(dú)立的發(fā)生故障，則圖G的可靠度為：

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

其中 Akm為特征值，所求網(wǎng)絡(luò)連通時(shí)Akm=1，所求網(wǎng)絡(luò)不連通時(shí)Akm=0.

展開(kāi)定理3[4]：

對(duì)一條邊一個(gè)頂點(diǎn)展開(kāi)

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

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

D=f00

f10為第i條邊通，第j個(gè)節(jié)點(diǎn)不通時(shí)網(wǎng)絡(luò)的可靠度；

f01為第i條邊不通，第j個(gè)節(jié)點(diǎn)通時(shí)網(wǎng)絡(luò)的可靠度；

f11為第i條邊，第j個(gè)節(jié)點(diǎn)都通時(shí)網(wǎng)絡(luò)的可靠度；

f00為第i條邊，第j個(gè)節(jié)點(diǎn)都不通時(shí)網(wǎng)絡(luò)的可靠度.

展開(kāi)定理3還可以進(jìn)一步推廣：

展開(kāi)定理3的推廣：其中的第i條邊可以推廣為包含有m個(gè)二度點(diǎn)的鏈，此時(shí)，這條鏈連通的概率為pm-11pm-22（不包含鏈的端點(diǎn)）用這個(gè)概率代替展開(kāi)定理3中的p1便可以得到一些較復(fù)雜圖的可靠度計(jì)算公式R（G）=APm-11pm-22+BP2+CPm-11Pm-12+D.其中A、B、C、D所代表的含義和定理3中類似，只需把第i條邊換成第i條鏈即可.

二、θ-圖的邊點(diǎn)網(wǎng)絡(luò)可靠度

θ-圖是所有n點(diǎn) n+1 邊圖中點(diǎn)可靠邊不可靠的一致最優(yōu)可靠圖，下面就應(yīng)用展開(kāi)定理3的推廣定理來(lái)計(jì)算θ -圖上兩個(gè)二度點(diǎn)的連通概率.

設(shè)C、D都為3度點(diǎn)A、B是這兩個(gè)3度點(diǎn)之間不在同一條邊上的任意兩個(gè)2度點(diǎn)，a、b、c、d、e、f、e分別為AD、AC、CB、BD、CD之間2度點(diǎn)的個(gè)數(shù)，現(xiàn)在就來(lái)計(jì)算AB連通的概率，根據(jù)推廣定理對(duì)鏈a和頂點(diǎn)D分解：分別作出f10，f01，f11，f00對(duì)應(yīng)的網(wǎng)絡(luò)如

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

至此得到了θ-圖的邊點(diǎn)可靠度多項(xiàng)式，它在網(wǎng)絡(luò)設(shè)計(jì)和優(yōu)化方面具有一定指導(dǎo)意義.

【參考文獻(xiàn)】

[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]趙沁平，王化奎.關(guān)于“邊點(diǎn)網(wǎng)絡(luò)”的可靠度.太原理工大學(xué)學(xué)報(bào)[J]1980，03：47-55.

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