顶点覆盖

顶点覆盖是在每条边的两个端点中至少承担一个。若边表示需要监测的直接连接，选中一个顶点便可同时负责所有与它关联的边；高次数顶点因而可能一次覆盖许多约束，但局部次数并不能决定全局最优组合。

从补集一侧看，未选中的顶点之间绝不能留有边。最小化覆盖人数与最大化可同时留下的互不相邻顶点是同一个选择的两面，等式 $\tau +\alpha =|V|$ 精确记录了这种互补，而非松散的近似关系。

在星图 $K_{1,n}$ 中，中心单点覆盖全部边，所以 $\tau =1$。所有 $n$ 片叶子也构成一个按包含极小的覆盖：删去任一叶都会漏掉它与中心之间的边。这个规模差距说明，逐点删不动只能证明局部极小，无法证明基数最优。

三角形至少要选两个顶点。任意单点都会漏掉另外两个顶点之间的边，而任意两点确实覆盖三条边，所以 $\tau (K_3)=2$。最大匹配只有一条边，匹配下界在这里不紧；奇圈正是二分图中等号性质失效的最小见证。

孤立顶点与任何边都不关联，最小覆盖无需选择它。无边图的空集就是顶点覆盖，因而 $\tau =0$。带自环的模型会强迫选择自环顶点；本页的简单图约定没有这项边界。

顶点覆盖选择顶点去碰到边；边覆盖选择边去碰到顶点；支配集则要求每个未选顶点邻接某个已选顶点。三种问题的“覆盖对象”不同，星图上虽然都容易画出，最优解与孤立点处理规则并不相同。

带权顶点覆盖为每个顶点给出成本并最小化总成本。一个昂贵中心与许多便宜叶子的星图可能放弃基数最优的中心单点，改选所有叶子；无权公式不能直接替代权重比较。

取任一极大匹配 $M$，把所有匹配边的两个端点都放入集合 $C$。若还有边的两个端点都不在 $C$，它就能加入 $M$，与极大性矛盾；所以 $C$ 是覆盖。又因为 $\nu (G)\le \tau (G)$，

这给出一般图最小顶点覆盖的简单二近似，并把“极大匹配足够”限定在近似保证上。

在二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。中，Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。把下界加强为精确等式 $\nu (G)=\tau (G)$。从最大匹配的交替搜索树还能直接构造同样大小的覆盖；一般图没有这项保证。

参数化算法利用每条未覆盖边 $uv$ 的二选一结构：任何大小至多 $k$ 的覆盖都必须包含 $u$ 或 $v$，于是分别选择一个端点并把预算减一。深度至多 $k$ 的分支树给出最基本的固定参数算法骨架，也清楚说明为何每个分支都保持完备。

网络监控、测试触点和冲突消解只有在“一端被选即可处理整条边”时才适合顶点覆盖。若一条风险需要两个端点共同处理，或约束一次涉及三个以上对象，模型必须增加不同的边语义或改用超图。