data-structures - 具有最少叶子的生成树

Question

所以我的问题如下：

我有一个无向（完整）加权图 G=(V,E)，我想生成所有可能的生成树，其叶子数最少，即最小顶点数为 1。让我们称这种树MIN_LEAF。

可能，我想直接在所有具有最小叶数的树中生成总权重最小的树（请注意，这不一定是最小生成树）。确定树 T 是否是给定图 G NP 完全的 MIN_LEAF 的问题？

如果是这样，我想知道是否存在某种启发式算法（贪婪或局部搜索），它至少可以为这个问题提供一个近似的解决方案。

提前致谢。

Answer 1

您描述的第一个问题 - 找到尽可能少的叶子的生成树 - 是NP -hard。您可以通过将哈密顿路径问题简化为这个问题来看到这一点：注意哈密顿路径是图的生成树，并且只有两个叶节点，并且恰好具有两个叶节点的图的任何生成树都必须是哈密顿量小路。这意味着确定图中是否存在哈密顿路径的NP难题可以通过找到图的最小叶生成树来解决：当且仅当最小叶生成树正好有两个叶时，路径才存在. 您描述的第二个问题包含第一个问题作为特例，因此也将是NP -hard。

一个快速的谷歌搜索出现了论文“关于找到几棵叶子的生成树”，这似乎是近似算法的一个很好的起点（它们有一个任意图的 2 近似值）和进一步阅读该主题。