具有加权顶点的树中最小权重的顶点覆盖

Question

给定一棵无向边树，其中一个顶点的权值是它的度，求出权值最小的顶点覆盖

我是这么想的:

由于顶点覆盖需要包含足够的顶点来覆盖所有边，这意味着无论覆盖中的顶点是什么，所有顶点的权重之和都是相同的(等于边的数量)。因此，我们不需要任何特殊的算法来找到答案，我们只需要找到最小大小的顶点覆盖(最小顶点覆盖)。

这是正确的，还是我错过了一些明显的东西?

Answer 1

这是正确的，还是我错过了一些明显的东西?

具有相同边的两个顶点;例如,…

A -- B -- C
Weights:
B = 2;
A = 1;
C = 1

{ A, C }和{ B }都是你定义的加权最小顶点覆盖。

只有{ B }是标准的最小顶点覆盖。

编辑:

…一个更好的例子显示了不同的原因:

A -- B -- C -- D
Weights:
B = 2;
C = 2;
A = 1;
D = 1

{ A, C }, { B, D }, { B, C }都是标准的极小顶点覆盖。

根据你的定义，只有{ A, C }和{ B, D }是加权最小顶点覆盖。直观地说，这是因为{ B, C }顶点覆盖对B -- C边缘进行了两次计数。

---

第一个反例反驳了所有加权mvp(根据你的定义)都是标准的mvp。第二个反例证明所有标准mvc都是加权mvc。

经过一番思考……你是正确的，因为树的加权MVC是代价等于边数的任何VC。

找到一个加权MVC实际上很简单。如果你画出树，并从每一层选择所有的顶点(不管你是从第一层还是第二层开始)，你最终得到一个有效的加权MVC(因为所有的边都被覆盖了，没有边被计数两次)。

…更一般地说，所有加权mvc的集合是所有不包含邻居的vc的集合。例如，在没有子节点为父节点的树中，叶节点集也是一个有效的加权MVC。