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

摘要

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