本文共 1763 字，大约阅读时间需要 5 分钟。

原文地址：

什么是握手引理（Handshaking Lemma）?

是关于无向图的。在每个有限的无向图中，奇数度的定点的个数总是偶数。握手引理是一个度数和公式的推论（有时候被称为握手引理）

$\sum_{v\in V} deg(v)=2|E|$

在树的数据结构中握手引理到底有啥用处？

下面是一些可以用握手引理证明的有趣实例：

1）在一个k-ary树种，树种每个节点要么没孩子，要么有k个孩子，下列特性恒为真。

L = (k - 1)*I + 1在这里 L = 叶子节点的数目      I = 内部节点的数目

证明：

证明可以分为两种情况：

情况1：（根节点是叶子节点）：树中只有一个节点。对于只有一个节点L=1，I=0，上面的式子是成立的。

情况2：（跟节点是内部节点）：对于多于一个节点的树，根一定是内部节点。上述的式子可以用握手引理证明。这个树是无向无环图。

树的总度数是节点数减一，例如：|E| = L + I – 1。

除了根，所有的内部节点在这种类型的树中的度数是k+1，根的度数是k。所有叶子节点的度数是1.将握手引理应用到这种树上，我们可以得到以下关系：

Sum of all degrees  = 2 * (Sum of Edges)  Sum of degrees of leaves +   Sum of degrees for Internal Node except root +   Root's degree = 2 * (No. of nodes - 1)  Putting values of above terms,     L + (I-1)*(k+1) + k = 2 * (L + I - 1)   L + k*I - k + I -1 + k = 2*L  + 2I - 2  L + K*I + I - 1 = 2*L + 2*I - 2  K*I + 1 - I = L  (K-1)*I + 1 = L

所以用握手引理证明上面的特性，我们再讨论一个更有趣的特性。

2）在二叉树中，叶子节点的数目总是比有两个孩子节点的数目多1。

L = T + 1在这里L=叶子节点的数目     T=带有两个孩子的内部节点的数目

证明：

设带有两个孩子的节点数目为T，可以分三种情况证明：

情况1：只有一个节点，那么关系为T = 0, L = 1。

情况2：根有两个孩子，例如：根的度是2：

Sum of degrees of nodes with two children except root +    Sum of degrees of nodes with one child +    Sum of degrees of leaves + Root's degree = 2 * (No. of Nodes - 1)      Putting values of above terms,   (T-1)*3 + S*2 + L + 2 = (S + T + L - 1)*2   Cancelling 2S from both sides.     (T-1)*3 + L + 2 = (S + L - 1)*2     T - 1 = L - 2     T = L - 1

情况3：根只有一个孩子，例如根的度是1：

Sum of degrees of nodes with two children +    Sum of degrees of nodes with one child except root +    Sum of degrees of leaves + Root's degree = 2 * (No. of Nodes - 1)      Putting values of above terms,   T*3 + (S-1)*2 + L + 1 = (S + T + L - 1)*2   Cancelling 2S from both sides.     3*T + L -1 = 2*T + 2*L - 2     T - 1 = L - 2     T = L - 1

因此在上面的三种情况中，我们得到T = L-1。

我们用握手引理讨论了树的两个重要的属性。

转载地址：http://ukhii.baihongyu.com/