一组顶点是一个顶点覆盖,当且仅当其补集是一个独立的集合时

问题描述 投票:0回答:1

此以下属性来自Wiki顶点覆盖:当且仅当其补集是独立集合时,一组顶点才是顶点覆盖。

我想知道我们如何证明这是真的?如果可以通过矛盾证明这一点很好,但所有其他证明方式也应受到赞赏。

谢谢!

graph graph-theory vertex vertex-cover
1个回答
0
投票

一些提示:

  • 如果我是一个独立集合,并且V-我不是顶点覆盖,那么在V-I中存在一个端点都没有端点的边。因此...?

  • 如果V-I是顶点覆盖,则选择任意边。如果两个端点都在I中,则...?

祝你好运!

© www.soinside.com 2019 - 2024. All rights reserved.