是否存在这样一个图，使得其最小顶点覆盖集（minimum vertex cover）包含其所有顶点？若不存在，如何证明？
littleMaple · 2021-02-06 01:23:08 +08:00 · 1569 次点击这是一个创建于 1405 天前的主题，其中的信息可能已经有所发展或是发生改变。
又因为最小顶点覆盖集（ minimum vertex cover ）是最大独立集（ maximum independent set ）的补集，所以问题也等价于「是否存在这样一个图，使得其最大独立集为空集？若不存在，如何证明？」
 |
1
Xs0ul 2021-02-06 01:50:39 +08:00 via Android  1
不确定我对定义的理解对不对，但感觉上全部顶点里，任意去掉其中一个顶点，剩下的集合是一个顶点覆盖集。
假设这个 N-1 个顶点组成的集合不是顶点覆盖集：首先全部顶点组成的集合肯定是顶点覆盖集，那么意味着去掉这个顶点导致至少有一条与这个顶点相连的边不再被覆盖。但是因为我们只去掉了一个顶点，所以这条边的另一个顶点覆盖了这条边，因此假设不成立。 于是最小顶点覆盖集至多只要 N-1 个顶点 |
 |
2
littleMaple OP @Xs0ul #1 感谢答复，你的反证法应该是正确的！非常优雅而简短。
|
|
3
littleMaple OP 仔细想了一下，还有另外一个证法，对任意一个图，其任意一个节点都是独立集，所以最大独立集的大小一定大于 1，又因为最大独立集是最小顶点覆盖集的补集，所以最小顶点覆盖集的大小一定小于等于 number of vertices minus one，得证.
|
 |
4
RecursiveG 2021-02-06 08:30:01 +08:00
其实如果允许一张图有 0 个点 0 条边，这个条件是成立的。
不允许这种情况的话就是一楼的证明. |
Select Language