顶点覆盖问题是图论中的经典组合优化问题。已被证明是NP完备的,具有较高的计算复杂性。本文主要研究无权图与加权图的最大独立集,目的是为了求解最小加权顶点覆盖。论文主要研究工作和成果包括以下几个方面:　　首先,对无权图的顶点覆盖和独立集进行了深入研究,在基于两者关系的基础上,得出结论,即在无权图中,对于任意一个顶点判断属于独立集比顶点覆盖简单。接着,在邻接矩阵与独立集自身特性的基础上,设计了一种基于邻接矩阵求解最大独立集的算法,进而解决最小顶点覆盖。通过实验验证算法的时间复杂度和正确性。　　其次,利用上述求解无权图的方法,同样从邻接矩阵与独立集自身特性入手,对加权图进行分析,并结合改进传统的贪婪算法,提出两个概念集合,即邻接集合和非邻接集合,设计一种基于贪婪算法求解最大加权独立集,进而求解最小加权顶点覆盖。同样通过实验验证算法的正确性和可行性。　　最后,文中对最大加权独立集在无线Ad hoc网络分簇算法方面的应用进行了研究。通过实验,将最大加权独立集算法和目前应用较为广泛的最小ID和最大节点的分簇算法分别对同一幅系统拓扑图进行求解,根据三种不同的结果图,说明本文算法的可行性与优越性。实验结果表明本文的算法可以达到解决簇首选择问题,从而改善网络中分级结构的最优服务质量问题。