这是最大叶生成树吗？

Question

这是无向失重图。我需要找到该图的最大叶生成树。我是否像这张照片一样制作了正确的最大叶生成树？谢谢你的回答。那么，叶子的最大数量是3？

Answer 1

图G的生成树是包含原图所有顶点的树。这里你的第一个图有 6 个顶点，而第二个图只有 5 个。它不包括顶点 F.

求最大叶子生成树。一个简单的解决方案也是找到最小连通支配集。你可以阅读更多关于它这里.

在这种情况下，最小连通支配集为 {B,E}。所以叶子将是其他四个顶点。