只有叶子的最小生成树？

Question

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

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

这里是问题的确切措辞

感谢帮助

Answer 1

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