图论在网络的可靠性分析中的应用—对基于1-critical-pathsubset网络的性能分析

Application of Graph Theory in Network Reliability -Reliability Analysis of Network Based on I-critical-path subset

本文对一种网络流模型的可靠性进行分析 .在这个模型中 ,我们考虑一对源节点和汇节点的图 ,它的弧是随机失效的 .当网络最大流大于正常工作流 ,我们就说系统是正常工作的 .考虑正常工作流的一种特殊情况 ,这里 ,所有的弧都具有相同的容量 .在这种特殊的情况中 ,潜在的系统是 1- critical的 ,也就是说 ,所有的弧的最小截大小为 2 .此时 ,问题转化为在有向图中 ,求所有的失效弧都在同一条路径上的概率 。

This paper addresses a class of reliability analysis model: a network flow model. For this model, we are given a capacitated source/sink graph in which arcs fail randomly. The system is defined as operating whenever the max-flow value is greater than a threshold. We address a special case of the threshold flow problem in which all arcs have the same capacity. For this special case we show that if the underlying system are 1-critical, namely, all arcs are in some cutset of size two, then this problem can be solved in polynomial time. The solution is obtained by reducing the problem to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path.