关键词: 点划分, 极小割集, 容斥原理, 网络可靠度, 算法

Abstract: The relation between node partition and cut set of an acyclic directed network was studied. The minimal cutsets could be obtained directly by partitioning the node set of network into two parts satisfying certain conditions. By the inclusion of the sets corresponding to the node portition, several cancellation rules for the terms in the expression of inclusion-exclusion principle were presented and proved to the network reliability. Using these rules, a formula expressing inclusion-exclusion principle and an algorithm for evaluating the reliability of acyclic directed networks were presented. The algorithm could give directly all the noncancellable terms in the inclusion-exclusion formula, of which the validity was illustrated by examples.