具有最少叶子数的生成树
Spanning Trees with minimum number of leaves
所以我的问题如下：
我有一个无向（完整）加权图 G=(V,E)，我想生成所有可能的生成树 且叶子数最少 ，即最小度数为 1 的顶点。我们称这种树为 MIN_LEAF.
可能，我想直接生成在所有叶子数最少的树中，也有最小总重量[=23]的树=]（请注意，这不一定是最小生成树）。
确定给定图 G 的树 T 是否为 MIN_LEAF 的问题是 NP 完全问题吗？
如果是这样，我想知道是否存在某种启发式算法（贪婪或局部搜索）至少可以给出该问题的近似解。
提前致谢。
您描述的第一个问题 - 找到尽可能少的叶子数量的生成树 - 是 NP-hard。您可以通过将哈密顿路径问题简化为这个问题来看到这一点：注意哈密顿路径是图的生成树并且只有两个叶节点，并且恰好有两个叶节点的图的任何生成树都必须是哈密顿量小路。这意味着确定图中是否存在哈密顿路径的 NP 难题可以通过找到图的 minimum-leaf 生成树来解决：路径存在，如果和仅当 minimum-leaf 生成树恰好有两个叶子时。您描述的第二个问题包含第一个问题作为特例，因此也将是 NP-hard.
快速 Google 搜索找到论文 "On finding spanning trees with few leaves"，这似乎是近似算法（它们对任意图有 2 次近似）和进一步阅读的良好起点关于这个问题。
所以我的问题如下：
我有一个无向（完整）加权图 G=(V,E)，我想生成所有可能的生成树 且叶子数最少 ，即最小度数为 1 的顶点。我们称这种树为 MIN_LEAF.
可能，我想直接生成在所有叶子数最少的树中，也有最小总重量[=23]的树=]（请注意，这不一定是最小生成树）。 确定给定图 G 的树 T 是否为 MIN_LEAF 的问题是 NP 完全问题吗？
如果是这样，我想知道是否存在某种启发式算法（贪婪或局部搜索）至少可以给出该问题的近似解。
提前致谢。
您描述的第一个问题 - 找到尽可能少的叶子数量的生成树 - 是 NP-hard。您可以通过将哈密顿路径问题简化为这个问题来看到这一点：注意哈密顿路径是图的生成树并且只有两个叶节点，并且恰好有两个叶节点的图的任何生成树都必须是哈密顿量小路。这意味着确定图中是否存在哈密顿路径的 NP 难题可以通过找到图的 minimum-leaf 生成树来解决：路径存在，如果和仅当 minimum-leaf 生成树恰好有两个叶子时。您描述的第二个问题包含第一个问题作为特例，因此也将是 NP-hard.
快速 Google 搜索找到论文 "On finding spanning trees with few leaves"，这似乎是近似算法（它们对任意图有 2 次近似）和进一步阅读的良好起点关于这个问题。