摘要
已知网络的割集,利用容斥原理求网络可靠度时,公式中会出现很多相互抵消的项.本文从割集出发,利用容斥原理中相消项的一个非常简单的性质给出一个求网络可靠度的简单而有效的容斥原理算法,证明了算法恰好给出了容斥原理表达中的不相消项,并且通过例子对算法的有效性进行了说明.
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.
出处
《小型微型计算机系统》
CSCD
北大核心
2007年第5期830-833,共4页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(60475036)资助
国家博士后基金项目(2003033372)资助
关键词
网络可靠度
容斥原理
极小割集
network reliability
inclusion-exclusion principle
mincut