网络可靠度分析的最小路算法和最小割算法研究

英文篇名：Comparison between path-based and cut-based algorithms for reliability analysis of networks
中文刊名：地震工程与工程振动
英文刊名：Journal of Earthquake Engineering and Engineering Vibration
作者：刘威 ; 李杰
英文作者：LIU Wei1 ; LI Jie1 ; 2 (1.Building Engineering Department ; Tongji University ; Shanghai 200092 ; China ; 2.Civil Engineering Disaster Prevention Lab ; Tongji University ; Shanghai 200092 ; China)
中文关键词：生命线工程 ; 可靠度 ; 最小路 ; 最小割 ; 递推分解算法
英文关键词：lifeline engineering ; reliability ; minimal path ; minimal cut ; recursive decomposition algorithm
出版日期：2008-06-15
机构：同济大学建筑工程系,同济大学建筑工程系上海200092,上海200092,同济大学土木工程防灾国家重点试验室,上海200092
年：2008
期：03
出版单位：地震工程与工程振动

摘要

网络可靠度分析是评价城市生命线工程系统整体抗震性能的主要手段。本文分别从最小路和最小割的角度介绍了网络可靠度分析算法,包括:经典不交最小路(割)算法、最小路(割)递推分解算法和改进最小路(割)递推分解算法。在此基础上,通过实例分析,着重进行了改进最小路递推分解算法和改进最小割递推分解算法的对比分析,分析结果表明两种算法在网络单元不同可靠度水平下具有不同的计算效率,并对引起以上区别的三个主要原因进行了分析。
The network connectivity reliability analysis is a main method to evaluate the seismic performance of lifeline engineering systems.In this paper,several algorithms for analyzing the network reliability are introduced,including disjoint minimal path(cut) algorithm,minimal path-based(cut-based) recursive decomposition algorithm and modified minimal path-based(cut-based) recursive decomposition algorithm.For a network with 17 nodes and 32 edges, modified minimal path-based recursive decomposition algorithm(MMPRDA) and modified minimal cut-based recursive decomposition algorithm(MMCRDA) are used to calculate the reliability and uhe results are compared.The results indicate that MMPRDA owns high efficiency for the networks owning high reliability edges while MMCRDA owns high efficiency for the networks owning low reliability edges.At last,three main reasons are analysed for the above results.

引文

[1]李杰.生命线工程抗震——基础理论与应用[M].北京:科学出版社,2005.
    [2]Fratta L,Montanari,UG.A recursive method based on case analysis for computing network terminal reliability[J].IEEE Trans Communica-tions,1978,26:1166-1177.
    [3]Aggarwal KK,Misra KB.A fast algorithm for reliability evaluation[J].IEEE Trans Reliability,1975,R-24(1):83-85.
    [4]Jie Li,Jun He.A recursive decomposition algorithm for network seismic reliability evaluation[J].Earthquake Engineering&Structural Dynam-ics,2002,31(8):1525-1539.
    [5]刘威.大型管网系统考虑腐蚀影响的抗震可靠性分析与优化[D].上海:同济大学,2007.
    [6]Yeh F M,Lu S K,Kuo S Y.OBDD-Based evaluation of k-terminal network reliability[J].IEEE Trans Reliability,2002,51(4):443-451.
    [7]李杰,刘威,钱摇琨.网络可靠度分析的最小割递推分解法[J].地震工程与工程振动,2007,27(5):33-39.
    [8]刘威,李杰.网络连通可靠度分析的改进最小割递推分解算法[J].同济大学学报,2008,36(4):427-431.
    [9]Lin PM,Alderson G E.Symbolic network functions by a single path-finding algorithm[C]//Proceedings of 7thAnnual Allerton Conference onCircuit and System Theory.1968:196-205.
    [10]廖炯生.网络可靠度的不交型算法(I)[J].宇宙学报,1982,(3):51-56.
    [11]廖炯生.网络可靠度的不交型算法(II)[J].宇宙学报,1982,(4):28-35.