基于网络化简和向量集分解的网络两终端可靠度算法  

Algorithm for computing two-terminal network reliability based on network simplification and vector set decomposition

作　　者：牛义锋[1] 徐秀珍[2] 李明奇[1] 

机构地区：[1]河南理工大学数学与信息科学学院,河南焦作454003 [2]河南理工大学计算机科学与技术学院,河南焦作454003

出　　处：《计算机应用研究》2010年第12期4750-4754,共5页Application Research of Computers

基　　金：河南理工大学青年基金资助项目(Q2010-35)

摘　　要：可靠度是衡量网络性能最重要的指标之一,不交和算法和因子分解算法是计算网络可靠度最重要的两种方法。不交和算法需要提前枚举网络所有极小路或极小割,因子分解算法虽然不需要枚举极小路或极小割,但每次只能分解一条边的状态。为了克服这两种算法的不足,基于网络化简和向量集分解,提出一个计算网络可靠度的高效、实用算法。该算法具有如下特点:a)算法首先求得网络的不可靠度,进而可得网络的可靠度;b)算法不需要提前枚举网络所有极小路和极小割;c)通过引入网络化简操作和向量集分解方法,算法每次可以分解多条边的状态,从而能更快速、更高效地实现对网络边的状态进行分解。最后通过实例以及与其他算法的比较验证了所提出算法的正确性和有效性。Reliability is one of the most important performance indexes of network. The sum-of-disjoint products algorithm and factoring decomposition algorithm are the most important algorithms for computing network reliability. Sum-of-disjoint products algorithm requires all MPs or MCs to be enumerated in advance; factoring decomposition algorithm doesn＇t require all MPs or MCs to be enumerated,but it only decomposes the states of one edge each time. In order to overcome the shortcomings of sum-of-disjoint products algorithm and factoring decomposition algorithm,this paper proposed an efficient and practical algorithm for computing network reliability based on network simplification and vector set decomposition. The proposed algorithm had the following characteristics：a） It first computed network unreliability,then obtained network reliability. b） It didn＇t require all MPs and all MCs to be enumerated in advance. c） By introducing the network simplification operations and vector set decomposition method,the proposed algorithm could decompose the states of more edges each time,so it could decompose the states of edges more quickly and more efficiently. Finally,verified the correctness and efficiency of the proposed algorithm by an exam-ple and comparisons with other algorithms.

关 键 词：网络可靠度 极小路 极小割 状态向量 网络化简 向量集分解 

分 类 号：TN913.2[电子电信—通信与信息系统] TP393[电子电信—信息与通信工程]