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

来源期刊：东北大学学报(自然科学版)2001年第5期

论文作者：孙艳蕊 张祥德 徐美进

文章页码：576 - 579

关键词：网络的连结矩阵;结点集合;极小割集;算法;

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