树上的顶点覆盖问题如下。
输入：无环简单无向图 G
输出：一组顶点 W 使得对于每条边 uv，u ∈ W 或 v ∈ W。我们希望最小化 W 的大小。
我的贪心算法是初始化 W = ∅，然后，当 G 不为空时，重复以下步骤。令 L 为 G 的叶顶点。令 N(L) 为与 L 中某个顶点相邻的顶点集。更新 W = W ∪ N(L)。从 G 中删除顶点 L ∪ N(L) 及其入射边。
该算法适用于我迄今为止尝试过的所有情况。我该如何证明它是正确的？这是我到目前为止所拥有的。
假设有另一个集合 S 是最优解。相反，我想确定 S 没有覆盖所有边缘，或者 S 与我的贪婪算法产生的集合相同。
这是一个合理的开始，但我看到了两个问题。首先，最优解可能不是唯一的。考虑四顶点路径a-b-c-d，它具有三个最优解：{a,c}, {b,c}, {b,d}。其次（你可能已经这样做了，但你没有这么说），有必要考虑树是有根的。否则，a-b例如，在图上，我们有L = {a,b}和N(L) = {b,a}，并且产生的顶点覆盖是W = {b,a}，这不是最优的。通过指定a为根，根据定义，它被排除在叶子集合之外。
为了正式证明涉及循环的程序的正确性，使用归纳法建立循环不变量通常是一个好主意。请允许我推荐两个。
对于所有时间 t（其中时间 = 循环迭代次数），令 G(t) 为 G 在时间 t 的剩余部分，并让 W(t) 为 W 在时间 t 的值。对于 G(t) 的每个顶点覆盖 X，集合 W(t) ∪ X 是 G(0) 的一个顶点覆盖，其中 0 是开始时间。
对于所有时间 t，存在一个包含 W(t) 作为子集的最优解。
设 T 为结束时间。由于 G(T) 是空图，X = ∅ 是 G(T) 的有效顶点覆盖，因此不变量 #1 确定 W(T) 是 G(0) 的顶点覆盖。不变量 #2 确定 W(T) 包含在某个最优解中。由于 W(T) 本身是一个顶点覆盖，因此 W(T) 本身必须是那个最优解。
证明不变量 #2 的归纳步骤是，给定一个包含 W(t-1) 但不包含 W(t) 的最优解，将其按摩成另一个包含 W(t) 的最优解。这涉及将您的直觉形式化，即将叶子的邻居带入叶子总是至少同样有效。