algorithm - 给定一个未加权的图，我如何找到具有 1 的生成树。最大叶数 2 最小叶数

Question

1. 编写一个算法来找到具有最大叶子数的生成树。
2. 编写一个算法以找到具有最少节点数的生成树。

我还无法为以下问题提出解决方案。

对于第一部分，我的想法是找到具有最高度数的顶点并将其放置在倒数第二层中，以便最后一层获得最大数量的叶子。

标签： algorithmgraphspanning-tree

Answer 1

1. 找到具有最大叶子数的图的生成树是一个 NP-Complete 问题。支配集问题有一个减少，它是 NP 完全的。

2. 找到具有最少叶子的图的生成树也是一个 NP-Complete 问题。假设如果图有一条哈密顿路径，那么图有一个只有两片叶子的生成树。因此，找到具有最小叶数的图的生成树等价于找出图是否具有哈密顿路径。

因此，对于这两个问题，您都需要开发近似算法。