计算无圈有向网络ST可靠性的一个新方法

A New Method for Computing ST Reliability of Acyclic Directed Networks

本文考虑计算无圈有向网络的ＳＴ可靠性问题（至少存在一条从源点ｓ到汇点ｔ的正常运行道路的概率）。文章引进了深度优先搜索（Ｄｅｐｔｈ－ＦｉｒｓｔＳｅａｒｃｈ）有序根树的概念并提出一个新的计算无圈有向网络ＳＴ可靠性的拓扑公式。以该公式为基础，我们利用ＤＦＳ方法提出一个新的计算无圈有向网络ＳＴ可靠性算法，它能生成简洁的可靠性表达式，进而有效地计算无圈有向网络的ＳＴ可靠性。

This paper studies the problem of computing the ST reliability,the probability that there exists at least an operative path from source s to sink t ,in an acyclic directed network It introduces a concept of DFS ordered root tree and presents a new topological formula for computing the ST reliability of acyclic directed networks Based on this formula,we present a new algorithm for computing reliability of acyclic directed networks by using Depth First Search This algorithm can generate a simple expression of reliability,and therefore can efficiently compute reliability of acyclic directed networks Two examples illustrate our conclusion