网络所有最小点割的路集矩阵算法  

Algorithm for Generating All Minimal Vertex-Cuts in a Network

作　　者：袁亚华[1] 

机构地区：[1]西北工业大学

出　　处：《系统工程与电子技术》1991年第10期16-20,共5页Systems Engineering and Electronics

摘　　要：本文提出了一种利用网络路集矩阵求所有最小点割的计算机算法。本算法对矩阵的列元素进行组合,以逻辑加运算获得网络的所有最小点割,具有规则明确、概念简单的特点。经实例计算表明本算法是可靠和有效的。文中还给出算法的步骤和框图,并举例对问题进行了说明。In this paper, a new algorithm is developed for finding all minimal vertex-cuts of a network. In the known path-set matrix A1, the fusion of every vertex Vj to the vertex Vi is accomplished by OR-ing, that is, logically adding every column j to column i(j≠i), So A2 can be obtained. From the matrix A2, the minimal vertex-cuts which contain two vertexs can be got. In general, with A2…, Ak known, all minimal vertex-cuts can be found. Finally, a network example is offered.

关 键 词：计算机 网络 路集 矩阵 计算 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]