求网络极小割集的一个新算法

定义了网络连结矩阵的两个变换,引入了L满秩矩阵与L非满秩矩阵的概念·证明了这两类特殊矩阵与网络连通性的关系·利用这一关系和定义的两个变换,给出了求网络极小割集以及与极小割集对应的结点集合的递推公式;建立了一个求网络所有极小割集及与之对应的结点划分集合的有效算法·算法只需对网络的连结矩阵进行处理,在计算机上实现起来很方便·最后通过实例说明了算法的有效性·

A New Algorithm for Generating all Minimal Cutsets in a Graph

Two transformations of connection matrix were defined,and the L full rank matrix and non full rank matrix were given. The relation between two special matrix and the connectivity of network was presented. By using the relation and these transformations two recursive formulas were given to get the entire minimal cutsets and the entire node sets corresponding to the cutsets, respectively. An efficient algorithm was set up to get the entire node sets and all the minimal cuts corresponding to the node sets. The algorithm only need managing the connection matrix of the network. It is very convenience to be realized. The efficiency of the algorithm was illustrated by experiments on Pentium 120 computer.