论文部分内容阅读
网络的最小割集等效是大系统可靠性评估中常常遇到的重要问题,也是出现“维数灾难”的主要原因。本文提出了一种快速分块算法,并从理论上对其正确性进行了证明。算法中的连通性判断采用了链表数据结构和深度遍历法(DFS)相结合的方法,从而有效地提高了判断连通性的速度。文中还提出了一种判断已知边集是否为最小割的方法。计算复杂性分析和网络可靠性评估的算例表明了该算法对大系统可靠性评估的有效性。
The minimum cut set equivalence of networks is one of the most important problems often encountered in the assessment of large-scale system reliability and also the main reason for the “dimensionality disaster”. In this paper, a fast partitioning algorithm is proposed, and its correctness is proved in theory. The connectivity in the algorithm uses a combination of linked list data structure and DFS to effectively improve the speed of determining connectivity. In the paper, a method of judging whether a known edge set is a minimum cut is also proposed. An example of computational complexity analysis and network reliability evaluation shows the effectiveness of this algorithm in large system reliability assessment.