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

An Inclusion-exclusion Algorithm for Network Reliability

作　　者：孙艳蕊[1] 赵连昌[2] 张祥德[1] 

机构地区：[1]东北大学理学院,辽宁沈阳110004 [2]大连海事大学数理系,辽宁大连116024

出　　处：《小型微型计算机系统》2007年第5期830-833,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60475036)资助;国家博士后基金项目(2003033372)资助

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

关 键 词：网络可靠度 容斥原理 极小割集 

分 类 号：TN913.21[电子电信—通信与信息系统]