是否存在这样一个图，使得其最小顶点覆盖集（minimum vertex cover）包含其所有顶点？若不存在，如何证明？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1188 天前的主题，其中的信息可能已经有所发展或是发生改变。

（腾讯云最新优惠活动来了：云产品限时1折，云服务器低至88元/年，点击这里立即抢购：9i0i.cn/qcloud，更有2860元代金券免费领取，付款直接抵现金用，点击这里立即领取：9i0i.cn/qcloudquan）

（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）

又因为最小顶点覆盖集（ minimum vertex cover ）是最大独立集（ maximum independent set ）的补集，所以问题也等价于「是否存在这样一个图，使得其最大独立集为空集？若不存在，如何证明？」

顶点

Vertex

minimum

Cover

4 条回复 ? 2021-02-06 08:30:01 +08:00

Xs0ul

2021-02-06 01:50:39 +08:00 via Android

不确定我对定义的理解对不对，但感觉上全部顶点里，任意去掉其中一个顶点，剩下的集合是一个顶点覆盖集。

假设这个 N-1 个顶点组成的集合不是顶点覆盖集：首先全部顶点组成的集合肯定是顶点覆盖集，那么意味着去掉这个顶点导致至少有一条与这个顶点相连的边不再被覆盖。但是因为我们只去掉了一个顶点，所以这条边的另一个顶点覆盖了这条边，因此假设不成立。

于是最小顶点覆盖集至多只要 N-1 个顶点

littleMaple

2021-02-06 02:05:24 +08:00

@Xs0ul #1 感谢答复，你的反证法应该是正确的！非常优雅而简短。

littleMaple

2021-02-06 02:26:53 +08:00

仔细想了一下，还有另外一个证法，对任意一个图，其任意一个节点都是独立集，所以最大独立集的大小一定大于 1，又因为最大独立集是最小顶点覆盖集的补集，所以最小顶点覆盖集的大小一定小于等于 number of vertices minus one，得证.

RecursiveG

2021-02-06 08:30:01 +08:00

其实如果允许一张图有 0 个点 0 条边，这个条件是成立的。
不允许这种情况的话就是一楼的证明.