在树中找到k个顶点以覆盖最大数量的边

Question

我的想法是贪婪的。

我维持E [i]为与顶点i连接的边数。

Repeat following k times:

    Every time I extract largest E[k] and add vertex k to the result set, and I decrease E[t] by 1 for every vertex t adjacent to k.

    Set E[k] = 0;

但是，我不知道我的想法正确与否。而且我也不知道如何证明它。

如果没有，什么是解决此问题的正确方法？

Answer 1

这种贪婪的方法是不正确。

让我们考虑要求您计算出下图中可以覆盖4个节点（k = 4）：

您的算法将选择节点1，然后从<2,3,4,5}]中选择3个节点]。

使用此选项，您将覆盖7条边线

，相反，您可以选择节点2、3、4和5并覆盖所有8条边线！