大门|大门-CS-2005 |问题11

设G是一个有20个顶点和100条边的简单图。G的最小顶点覆盖的大小为8。然后，G的最大独立集的大小为 （A） 12 （B） 8. （C） 少于8 （D） 超过12个 答复: （A） 说明： 背景说明： 顶点覆盖 是一组图的顶点，使得图的每条边都与S的至少一个顶点相关联。 独立集 图的顶点集是一组顶点，使得该集中的所有顶点都没有连接它们的边，也就是说，没有两个顶点是相邻的。单个顶点是一个独立集，但我们感兴趣的是最大独立集，即最大独立集。

独立集与顶点覆盖的关系： 一个有趣的事实是，图的顶点数等于其最小顶点覆盖数加上最大独立集的大小。怎样移除最小顶点覆盖的所有顶点将导致最大独立集。

如果S是G（V，E）的最小顶点覆盖的大小，那么 G的最大独立集为| V |–S。

解决方案： 最小顶点覆盖的大小=8 最大独立集的大小=20–8=12 因此，正确答案是（A）。

参考资料： 顶点覆盖 最大独立集 .

这个解决方案是由 尼蒂卡·班萨尔。 这个问题的小测验