链路失效情况下网络点对联通可靠度的近似计算

基于联通性的网络可靠性分析是网络可靠性研究中的经典问题,根据具体问题的不同而采用的最小枚举、最小生成树枚举、边割集枚举、容斥原理、不交和方法等都是随机性网络可靠性指标的精确计算方法。这些计算方法在网络可靠性分析研究中具有重要的作用和意义,它们构成了网络可靠性分析计算的重要理论依据。然而对任意网络的k终端可靠度、全终端可靠度以及剩余边联通可靠度和点对联通可靠度,都已经证明他们的精确计算属于NP-hard问题。网络可靠性的估计是获得以上可靠性测度的重要手段,同时在网络的拓扑优化设计中,追求高可靠性的代价就是费用的无限增加,在一般商用的设计中,网络可靠性测度只要满足给定的标准即可,需要对不同的网络拓扑估计有关的可靠性值。