计算无圈有向网络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