握手引理

握手定理讨论的是无向图。在每一个有限无向图中，奇数度的顶点总是包含在偶数个顶点中。 度数和公式以握手定理的形式展示了结果。

握手定理在树数据结构中的应用

使用握手定理，我们可以证明以下各种有趣的事实：

1. 以下属性在 k 叉树中始终为真，其中每个节点都有 0 或 k 个子节点。

其中

L 表示叶子节点的数量

I 表示内部节点的数量

证明

我们将证明分为以下两种情况：

情况 1： 在这种情况下，我们将证明 根是叶子。该树仅包含一个节点。对于单个节点，上述公式成立，因为 I = 0，L = 1。

情况 2： 在这种情况下，我们将证明 根是内部节点。如果树包含多个节点，则根始终是内部节点。 对于这种情况，我们可以使用握手定理来证明上述公式。 一棵树可以表示为无向无环图。

树中的节点数： 可以计算边的总数，即：

在这种类型的树中，除了根之外，所有内部节点都具有 k + 1 度。根包含度 k，所有叶子包含度 1。 当这样的树应用握手定理时，我们将得到以下关系：

当我们放入上述项的值时，我们将得到以下结果：

我们已经看到，当我们使用握手定理时，可以证明上述属性。 现在，我们将学习另一个有趣的属性。

替代证明： 在这种情况下，我们将不使用握手理论。

由于该树有 I 个内部节点，并且每个内部节点都有 K 个子节点。 因此，子节点的总数 = k * I。

因此，我们有 I - 1 个内部节点，它们是其他节点的子节点。它排除了根，即：

内部节点是 k * I 个子节点中的 I - 1 个。 因此，叶子描述为 (K*I - (I - 1))。

因此

2. 二叉树中叶节点的以下属性数始终比具有两个子节点的节点多一个。

其中 L 表示叶子节点数

T 表示内部节点的子节点，它有两个子节点。

证明： 为此，我们将假设 T 为具有两个子节点的节点数。 我们将证明分为以下三种情况：

情况 1： 该关系仅由一个节点 L=1, T =0 保持

情况 2： 当根包含两个子节点时，则根的度为 2。

具有两个子节点的节点的度数之和（根除外）+ 具有一个子节点的节点的度数之和 + 叶子的度数之和 + 根的度数 = 2 * (节点数 -1)

当我们放入上述项的值时，我们将得到以下结果：

当我们从两边都取消 25 时，我们将得到以下结果：

情况 3： 当根包含一个子节点时，则根的度为 1。

具有两个子节点的节点的度数之和 + 具有一个子节点的节点的度数之和（根除外）+ 叶子的度数之和 + 根的度数 = 2 * (节点数 -1)

当我们放入上述项的值时，我们将得到以下结果：

当我们从两边都取消 25 时，我们将得到以下结果：

因此，我们在以上所有三种情况下都得到 T = L-1。

使用握手定理，讨论了树的两个重要属性。