大系统可靠性评估的快速分块算法

网络的最小割集等效是大系统可靠性评估中常常遇到的重要问题,也是出现“维数灾难”的主要原因。本文提出了一种快速分块算法,并从理论上对其正确性进行了证明。算法中的连通性判断采用了链表数据结构和深度遍历法(DFS)相结合的方法,从而有效地提高了判断连通性的速度。文中还提出了一种判断已知边集是否为最小割的方法。计算复杂性分析和网络可靠性评估的算例表明了该算法对大系统可靠性评估的有效性。