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

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

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

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

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

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

注意

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