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

Question

给定一棵具有无向边的树，其中顶点的权重是它的度，找到最小权重的顶点覆盖。

这是我的想法:

由于顶点覆盖需要包含足够的顶点来覆盖所有边，这意味着无论覆盖中的顶点如何，所有顶点的权重之和都将相同(等于边数) .因此，我们不需要任何特殊的算法来寻找答案，我们只需要找到最小尺寸的顶点覆盖(cover with minimum vertices)。

这是正确的，还是我遗漏了一些明显的东西？

Answer 1

Is this correct, or am I missing something obvious?

具有相同边的两个顶点；例如，...

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 边计数了两次。

---

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

经过一番思考...您是正确的，因为树的加权 MVC 是成本等于边数的任何 VC。

找到加权 MVC 其实很简单。如果你画出树，并从每第二层中挑选所有顶点(不管你是从第一层还是第二层开始)，你最终会根据你的定义得到一个有效的加权 MVC(因为所有边都被覆盖了，没有边缘被计算两次)。

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