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

Comparison between path-based and cut-based algorithms for reliability analysis of networks

作　　者：刘威[1] 李杰[1] 

机构地区：[1]同济大学建筑工程系,上海200092

出　　处：《地震工程与工程振动》2008年第3期33-38,共6页Earthquake Engineering and Engineering Dynamics

基　　金：国家自然科学基金委创新研究群体资助项目(50621062)

摘　　要：网络可靠度分析是评价城市生命线工程系统整体抗震性能的主要手段。本文分别从最小路和最小割的角度介绍了网络可靠度分析算法,包括:经典不交最小路(割)算法、最小路(割)递推分解算法和改进最小路(割)递推分解算法。在此基础上,通过实例分析,着重进行了改进最小路递推分解算法和改进最小割递推分解算法的对比分析,分析结果表明两种算法在网络单元不同可靠度水平下具有不同的计算效率,并对引起以上区别的三个主要原因进行了分析。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 cutbased recursive decomposition algorithm（MMCRDA） are used to calculate the reliability and the 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.

关 键 词：生命线工程 可靠度 最小路 最小割 递推分解算法 

分 类 号：P315.95[天文地球—地震学]