文件名称：逆序启发式算法求解近似最小支配集的实现
文件大小：2KB
文件格式：NONE
更新时间：2012-10-12 09:27:06
最小支配集
逆序启发式算法求解近似最小支配集的具体算法： 步骤1 将V中的顶点度数从小到大进行排序成点集 ，并将全部顶点设置成未标号； 步骤2 取V‘中第一个顶点，若该顶点已经标号，并在 中删除该点，转至步骤3；否则，将该点标号为1，并将与之相关联且未标号的顶点标号为0，在 删除该点； 步骤3 若 为空，转至步骤4；否则转至步骤2； 步骤4 取标号为1的顶点作为支配集，把这些点组成的点集作为极小支配集。 按照上述的算法我们对点集V 按照逆序排列得到 ，最后求出标号为1的所有点，它们所组成的集合即为所求。