algorithm - 如何测试一棵树是否在线性时间内具有完美匹配？

Question

给出一个线性时间算法来测试一棵树是否具有完美匹配，也就是说，一组边恰好与树的每个顶点接触一次。

这是来自 S. Dasgupta 的算法，我似乎无法确定这个问题。我知道我需要以某种方式使用贪婪的方法，但我就是想不通。帮助？

伪代码很好；一旦我有了想法，我可以用任何语言轻松实现。

算法必须是线性的。 O( V + E ) 没问题。

Answer 1

我想我有解决办法。因为我们知道图是一棵树，所以我们知道叶节点的存在，即只有一条边且没有子节点的节点。为了使该节点包含在完美匹配中，该边必须存在于最终解决方案中。

因此，我们可以找到连接到叶节点的所有边，添加到解决方案中，并从图中删除接触的边。如果在此过程结束时，我们留下任何未触及的剩余节点，则不存在完美匹配。