algorithm - 只有叶子的最小生成树？

Question

我被要求编写一个算法，在图 G 中找到最小生成树，但条件是 G 的每个顶点都是生成树 T 中的一个叶子。如果图有两个以上的元素，这怎么可能？假设 G 包含顶点 a、b 和 c，生成树可能类似于 a--b--c，因此在这种情况下 b 不是叶子。

我不是在寻找算法的解决方案，我只想了解生成树如何完全由叶子组成。

这是问题的确切措辞

谢谢您的帮助

Answer 1

该问题指出 S 是图中顶点 V 的子集。可能有非叶节点。但是，您必须确保这些内部节点不在 S 中。如果 S 等于 V，那么您是对的。