计算网络可靠度的容斥原理算法

An Inclusion-exclusion Algorithm for Network Reliability

已知网络的割集,利用容斥原理求网络可靠度时,公式中会出现很多相互抵消的项.本文从割集出发,利用容斥原理中相消项的一个非常简单的性质给出一个求网络可靠度的简单而有效的容斥原理算法,证明了算法恰好给出了容斥原理表达中的不相消项,并且通过例子对算法的有效性进行了说明.

The inclusion-exclusion formula （IEF） of the reliability of a network starting with cutsets may contain many pairs of terms of that cancel each other. Using a very simple characteristic of canceling terms in IEF, this paper presents a simple and efficient inclusion-exclusion algorithm for evaluating the reliability of a network starting with cutsets. It is proved that the terms of the algorithm generating are just the non-canceling of IEF expression. And the efficiency of the algorithm is illustrated by examples.