最小支配集-最小点覆盖-最小边覆盖
最小点覆盖 (Minimum Vertex Cover, MVC)
- 用最少数量的顶点覆盖图中所有的边。
最小边覆盖 (Minimum Edge Cover, MEC)
- 用最少数量的边覆盖图中所有的顶点。
最小支配集 (Minimum Dominating Set, MDS)
- 用最少数量的顶点支配图中所有的顶点。
注意
- 注意区分最小点覆盖和最小支配集,两者一个考虑点一个考虑边
- 对于
A-B-C-D-E-F,最小点覆盖是3,最小支配集是2
A-B-C-D-E-F,最小点覆盖是3,最小支配集是2相关推荐