顶点覆盖数

顶点覆盖数是图 中最小顶点覆盖的大小，被称为图 的顶点覆盖数，记为 。

柯尼希-埃格瓦里定理指出，对于二分图，匹配数（即最大独立边集的大小）和顶点覆盖数相等。

图 的独立数 和顶点覆盖数通过下式关联：

其中 是顶点计数 (West 2000)。