最小顶点覆盖

最小顶点覆盖是对于给定图，顶点数最少的顶点覆盖。图 的最小顶点覆盖的大小被称为顶点覆盖数，记为 。

每个最小顶点覆盖都是极小顶点覆盖（即，不是任何其他覆盖的真子集的顶点覆盖），但反之不一定成立。

找到一般图的最小顶点覆盖是一个 NP 完全问题。然而，对于二分图，柯尼希-埃格瓦里定理允许在多项式时间内找到最小顶点覆盖。

图的最小顶点覆盖可以使用 Wolfram 语言计算，使用FindVertexCover[g]。目前没有 Wolfram 语言函数来计算所有最小顶点覆盖。

最小顶点覆盖对应于最大独立顶点集的补集。