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

摘要

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