点覆盖问题是一个著名的NP完全问题,虽然该类型问题的复杂度很高,但在日常生活中的应用非常广泛。比如,大型网络监控节点的布置,人员排班,超大规模集成电路芯片的设计等等。论文主要工作有以下几点：(1)以广义Petersen图和循环图为研究对象,研究图的最小点覆盖集精确算法中分支限界策略的应用,对尽可能大规模图的最小点覆盖问题进行计算,从而得到最小点覆盖集可扩展的构造方法,总结其最小点覆盖数上界公式；然后通过数学证明,得到下界；利用上下界逼近,最终确定C(n,2)、C(n,3), C(n,4)以及P(n,2),P(n,3)的精确最小点覆盖数。(2)为了解更大规模的网络图的最小点覆盖性质,本文还对最小点覆盖近似算法进行一些初步研究,以蛋白质互作用网络为主要研究对象,计算其近似最小点覆盖集。(3)搭建了最小点覆盖问题的计算实验平台,为课题组继续对最小点覆盖及相关问题的研究奠定平台基础,包括数据导入、算法实验、图形显示等功能。