顶点覆盖

顶点覆盖（vertex cover）是一个顶点集合，使图中每条边至少有一个端点被选入。它把“处理哪些顶点，才能碰到全部边”写成精确的组合条件。本文讨论有限无向简单图；最少需要选择的顶点数记为 $\tau (G)$。

例如，图的边为 $ab,ac,bc,cd,de$。选择 $C=\{b,c,d\}$：边 $ab$ 接着 $b$，边 $ac$ 接着 $c$，边 $bc$ 接着两者，边 $cd$ 接着 $c,d$，边 $de$ 接着 $d$。五条边全部被覆盖，且一条边被覆盖两次并无问题。

所选对象是顶点，覆盖目标是边。未选a、e互不相邻。

定义、极小与最小

对 $G=(V,E)$，集合 $C\subseteq V$ 是顶点覆盖，当且仅当 $$\mathrm{\forall }\{u,v\}\in E,u\in C\text{或}v\in C.$$ 若删除 $C$ 中任意顶点后都不再覆盖全部边，称它为极小顶点覆盖；若大小在所有覆盖中最小，称最小顶点覆盖，大小为 $\tau (G)$。最小必极小，极小不必最小。例如三点路径 $a-b-c$ 中，$\{a,c\}$ 是极小覆盖，因为去掉任一个都会漏边；但 $\{b\}$ 更小。

无边图的空集已覆盖全部边，因此 $\tau =0$。孤立顶点从不需要选入最小覆盖，因为它不覆盖任何边。对于存在边的图，整个顶点集总是覆盖，所以最小值一定存在。

与独立集的互补关系

一个独立集内任意两个不同顶点之间没有边。顶点覆盖与独立集有精确对应： $$C\text{为顶点覆盖}⟺V\setminus C\text{为独立集}.$$

证明。 若 $C$ 是覆盖而补集内有边 $uv$，两个端点都不在 $C$，这条边便没有被覆盖，矛盾。反过来，若补集独立，任何边都不可能两个端点同时留在补集，故至少一个端点在 $C$，满足覆盖条件。

令 $\alpha (G)$ 为最大独立集大小，顶点数为 $n$。由对应关系，每个覆盖的补集大小为 $n-\mathrm{\#}C$；将覆盖大小最小化，恰好使补集最大化，得到 $$\tau (G)+\alpha (G)=n.$$ 这里必须是最大独立集与最小覆盖，任意极大独立集只对应极小覆盖，不保证大小最优。

主例的最优性证明

主例的覆盖 $\{b,c,d\}$ 大小为三，给出上界。为证明两点不够，观察三角形 $abc$ 至少要选两个顶点：只选一个会留下另两点间的那条边。边 $de$ 又要求从 $d,e$ 至少选一点，而它们不在三角形中。因此任何覆盖至少有 $2+1=3$ 点。上下界合并得 $\tau (G)=3$。

按互补关系，$\{a,e\}$ 是大小二的最大独立集。也可直接检查：三角形内至多取一，$de$ 两点内至多取一，故独立集至多二，恰与构造吻合。

变式。 删除三角形中的边 $ab$，其余不变。此时 $\{c,d\}$ 覆盖 $ac,bc,cd,de$，大小二；而边 $ac$ 和 $de$ 端点完全分离，一个顶点不可能同时覆盖它们，所以最小值为二。补集 $\{a,b,e\}$ 成为大小三的最大独立集。

匹配给出的下界及其边界

匹配是一组两两没有公共端点的边。若一个匹配有 $k$ 条边，每条都要求覆盖集合至少提供一个端点，而这些端点不能由同一个顶点兼任，所以任何覆盖至少有 $k$ 个顶点。令最大匹配大小为 $\nu (G)$，即有 $$\nu (G)\le \tau (G).$$ 主例最大匹配大小为二，例如 $\{ab,de\}$；由于只有五个顶点，不可能有三条互不接触的边。这里 $\nu =2<3=\tau$，所以一般图中不能把这个下界直接当作等式。二分图上二者相等是 Kőnig 定理的内容，需要二分图条件与额外证明。

顶点覆盖也不同于支配集：前者要求每条边被所选端点碰到，后者要求每个未选顶点都有已选邻居。三角形中一个顶点已能支配全图，却不能覆盖另两个顶点之间的边；故支配集条件不能替代覆盖条件。