graph - 给定内部顶点数的树的叶子

Question

如果 T 是一棵树，并且给定 T 的内部（非叶子）顶点的度数之和为 50。如果 T 有 13 个内部顶点，它有多少叶子？我知道握手引理的概念，其中度数加起来是边数的两倍，并且会有（n-1）个边。但是我对如何显示这个总和的工作方式（不是任何代码）感到非常困惑。我可以期待一些帮助吗？

标签： graphtreetheory

Answer 1

所以我们得到了两个数字：

• = 内部顶点数
• = 内部顶点度数之和

请求的输出是：

• =叶子的数量

度数的总和是树中边数的两倍，随着叶子的数量而减少，因为它们的边只计入其父级的度数中：

      = 2 -

因为树中的边数比顶点数少一，所以我们还有：

      = + - 1

所以我们可以代入第一个等式：

      = 2( + - 1) - = 2 + - 2

现在解决这个问题：

      = + 2 - 2

对于您的示例，我们有以下输入：

      = 50, = 13

所以我们得到：

      = 26