图的支配集及其扩展是图论中的经典组合优化问题,在优化理论、城市交通路线规划、通信等领域中有广泛应用。然而,最小支配集及其扩展问题已被证明为NP难问题,已有近似求解算法的复杂度和精度有待进一步改进。本文结合粗糙集理论研究了无向图的最小支配集求解方法,主要工作及创新点包括以下几个方面:1.基于粗糙集理论中的属性序思想,提出了顶点序下无向图极小支配集求解算法。首先,在给定无向图顶点集上定义一个全序关系（即,顶点序）,进而在顶点闭邻接集集合上定义一个二元等价关系;然后,基于该二元等价关系提出了一种顶点序下的极小支配集算法;最后,证明了该算法在给定顶点序下求解相应极小支配集的完备性与唯一性,通过实例验证了算法的正确性和有效性。2.基于粗糙集理论中决策表属性约简原理,提出了无向图的一种启发式最小支配集近似算法。首先,利用图的邻接矩阵构造一个诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价;其次,基于诱导决策表的特征,采用前后向搜索机制和诱导决策表正域的累积计算策略,提出了一种复杂度较低的启发式最小支配集近似算法;最后,在公用数据集上与典型算法进行了实验对比,结果表明该算法在运行时间方面具有明显优势,且能得到更高精度的近似最小支配集。3.针对动态图提出了一种增量式支配集更新算法。首先,分析了支配集在无向图四种基本动态变化（插入顶点、删除顶点、插入边、删除边）下的特点,由此给出了相应的支配集更新策略;然后,提出了动态图的一种极小支配集增量式更新算法;最后,通过在公开的数据集上与非增量式算法进行了实验对比,验证了增量式更新算法的正确性和有效性。综上所述,本文在无向图的最小支配集近似求解算法方面取得了一些进展,有助于进一步研究最小支配集及其扩展问题,有望促进粗糙集理论与图论研究的新思路。