V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
littleMaple
V2EX  ›  算法

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

  •  
  •   littleMaple · 2021-02-06 01:23:08 +08:00 · 1388 次点击
    这是一个创建于 1147 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    4 条回复    2021-02-06 08:30:01 +08:00
    Xs0ul
        1
    Xs0ul  
       2021-02-06 01:50:39 +08:00 via Android   ❤️ 1
    不确定我对定义的理解对不对,但感觉上全部顶点里,任意去掉其中一个顶点,剩下的集合是一个顶点覆盖集。

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

    于是最小顶点覆盖集至多只要 N-1 个顶点
    littleMaple
        2
    littleMaple  
    OP
       2021-02-06 02:05:24 +08:00
    @Xs0ul #1 感谢答复,你的反证法应该是正确的!非常优雅而简短。
    littleMaple
        3
    littleMaple  
    OP
       2021-02-06 02:26:53 +08:00
    仔细想了一下,还有另外一个证法,对任意一个图,其任意一个节点都是独立集,所以最大独立集的大小一定大于 1,又因为最大独立集是最小顶点覆盖集的补集,所以最小顶点覆盖集的大小一定小于等于 number of vertices minus one,得证.
    RecursiveG
        4
    RecursiveG  
       2021-02-06 08:30:01 +08:00
    其实如果允许一张图有 0 个点 0 条边,这个条件是成立的。
    不允许这种情况的话就是一楼的证明.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4125 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 10:12 · PVG 18:12 · LAX 03:12 · JFK 06:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.