一个求无向图所有极大独立集的算法

An Algorithm for Generating all Maximum Independent Sets in an Undirected Graph

图的极大独立集在计算机视觉、计算机网络、编码理论和资源配置等领域有着广泛的应用.本文利用图的分解方法给出了一个求简单无向图所有极大独立集的递归公式.定义了图的邻接矩阵的两个变换和点集合的一些运算.在此基础上,利用二分树给出了一个求无向图的所有极大独立集的有效算法.算法的时间复杂度是O(mn),其中m,n分别是图的所有极大独立集数和顶点个数.算法只需对网络的邻接矩阵进行处理,在计算机上实现起来非常方便.最后,通过实例验证了算法的有效性.

The maximal independent set of a graph has a number of applications in areas such as computer vision, computer network, coding theory, resource placement, etc. A recursive formula was given to get all the maximum independent sets in a simple undirected graph by the decomposition of the graph. Two transformations of adjacency matrix of a graph and some operations of node sets were defined. By using the formula and these transformations an efficient algorithm was set up to get all the maximum independent sets in a simple undirected graph. The computational complexity of the algorithm is O （mn ）, where m and n are the numbers of maximum independent sets and nodes of the given graph respectively. The algorithm only need to deal with the adjacency matrix of the graph. It is very convenient to be realized. The efficiency of the algorithm was illustrated by experiment.