最小支配集-最小点覆盖-最小边覆盖

最小点覆盖 (Minimum Vertex Cover, MVC)

  • 用最少数量的顶点覆盖图中所有的

最小边覆盖 (Minimum Edge Cover, MEC)

  • 用最少数量的覆盖图中所有的顶点

最小支配集 (Minimum Dominating Set, MDS)

  • 用最少数量的顶点支配图中所有的顶点

注意

  • 注意区分最小点覆盖和最小支配集,两者一个考虑点一个考虑边
  • 对于A-B-C-D-E-F,最小点覆盖是3,最小支配集是2
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务