algorithm - 如何证明树上顶点覆盖的贪心算法的正确性？

Question

树上的顶点覆盖问题如下。

输入一个无环简单无向图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 与我的贪婪算法生成的集合相同。

Answer 1

这是一个合理的开始，但我看到两个问题。首先，最优解可能不是唯一的。考虑四顶点路径 a-b-c-d，它有三个最优解:{a,c}, {b,c}, {b,d}。其次(您可能已经这样做了，但您没有这么说)，有必要考虑将树生根。否则，例如在图 a-b 上，我们有 L = {a,b} 和 N(L) = {b,a} ，并且生成的顶点覆盖是 W = {b,a}，这不是最优的。通过将 a 指定为根，根据定义它被排除在叶子集合之外。

为了正式证明包含循环的程序的正确性，使用归纳法建立循环不变量通常是个好主意。请允许我提出两个建议。

1. 对于所有时间 t(其中时间 = 循环迭代次数)，设 G(t) 为 G 在时间 t 的剩余部分，W(t) 为 W 在时间 t 的值。对于G(t)的每一个顶点覆盖X，集合W(t)∪X是G(0)的一个顶点覆盖，其中0是开始时间。

2. 对于所有时间 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) 的最优解。这涉及将您的直觉形式化，即将一片叶子的邻居移到另一片叶子上至少总是同样有效。