握手引理和有趣的树性质-yiteyi-C++库

什么是握手引理？ 握手引理是关于一个无向图的。在每个有限无向图中，偶数个顶点总是有奇数度。握手引理是度和公式的结果（有时也称为握手引理） $sum_{u epsilon v} deg(v) = 2left | E ight |$

null

握手引理在树数据结构中是如何有用的？ 下面是一些可以用握手引理证明的有趣事实。

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

  L = (k - 1)*I + 1Where L = Number of leaf nodes      I = Number of internal nodes

证据： 证据可分为两种情况。

案例1 （根是叶）：树中只有一个节点。上述公式适用于L=1、I=0的单个节点。

案例2 （根是内部节点）：对于具有多个节点的树，根始终是内部节点。在这种情况下，可以用握手引理证明上述公式。树是一个无向无环图。

树中的总边数是节点数减去1，即| 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

利用握手引理证明了上述性质，让我们讨论一个更有趣的性质。

替代证据： （不使用握手定理）由于有I个内部节点，每个节点都有K个子节点，因此树中的子节点总数=K*I。

I-1内部节点是其他节点的子节点（根节点已被排除，因此比内部节点总数少一个）

也就是说，在这些K*I子节点中，I-1是内部节点，因此其余（K*I–（I-1））是叶子。

因此L=（K-1）*I+1。 2）在二叉树中 叶节点的数量始终比具有两个子节点的节点多一个。

   L = T + 1Where L = Number of leaf nodes      T = Number of internal nodes with two children

证据： 设多个节点中有2个子节点为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 = (T + 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。

我们用握手引理讨论了树的两个重要性质的证明。很多关于这些房产的问题都被问到了，下面是几个链接。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章