形式陈述

无向图 $G=(V,E)$$G=(V,E)$ 的顶点覆盖是子集 $C\subseteq V$$C\subseteq V$，使每条边至少有一个端点属于 $C$$C$：

$$ \forall uv\in E, \quad u\in C\ \text{或}\ v\in C. $$$$\mathrm{\forall }uv\in E,u\in C\text{或}v\in C.$$

最小顶点覆盖大小记为 $\tau(G)$$\tau (G)$。补集 $V\setminus C$$V\setminus C$ 是独立集，且该对应双向成立，因此有限图中

$$ \tau(G)+\alpha(G)=|V|, $$$$\tau (G)+\alpha (G)=|V|,$$

其中 $\alpha(G)$$\alpha (G)$ 是最大独立集大小。任意匹配的边彼此不共享端点，覆盖每条匹配边至少需一个不同顶点，所以

$$ \nu(G)\le\tau(G), $$$$\nu (G)\le \tau (G),$$

其中 $\nu(G)$$\nu (G)$ 为最大匹配大小。

直觉

顶点覆盖选择一批监控点，使每条边都被至少一端监控。未选择的顶点之间不能再有边，因此它们恰组成独立集。

例子与边界

星图 $K_{1,n}$$K_{1,n}$ 的中心单点构成最小顶点覆盖；三角形最小覆盖大小为二。顶点覆盖与边覆盖不同：后者选择边来覆盖顶点。最小是基数最小，不是按包含极小；一个按包含不能删点的覆盖仍可能比最优大。一般图上最小顶点覆盖是 NP-hard，但二分图上由 Kőnig 定理可通过最大匹配多项式时间求解。带权版本最小化顶点权重之和，与无权大小版本不同。孤立顶点无需进入任何顶点覆盖。

推论与应用

顶点覆盖建模监控部署、冲突消除、测试选择，并与独立集、匹配和参数化算法紧密相连。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Ch. 2, matchings and covers。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Ch. 3, vertex covers, independent sets, and matchings。