Lema del apretón de manos y propiedades interesantes del árbol

¿Qué es el lema del apretón de manos?  
El lema del apretón de manos se trata de un gráfico no dirigido. En todo grafo no dirigido finito, un número par de vértices siempre tendrá un grado impar. El lema del apretón de manos es una consecuencia de la fórmula de suma de grados (a veces también llamado lema del apretón de manos) 

¿Cómo es útil Handshaking Lemma en la estructura de Tree Data?  
Los siguientes son algunos hechos interesantes que se pueden probar usando el lema Handshaking. 

1) En un árbol k-ario donde cada Node tiene 0 o k hijos, la siguiente propiedad siempre es cierta. 

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

Prueba: 
La prueba se puede dividir en dos casos. 

• Caso 1 (La raíz es hoja): Solo hay un Node en el árbol. La fórmula anterior es cierta para un solo Node como L = 1, I = 0. 
• Caso 2 (La raíz es un Node interno): Para árboles con más de 1 Node, la raíz siempre es un Node interno. La fórmula anterior se puede probar usando Handshaking Lemma para este caso. Un árbol es un grafo acíclico no dirigido. 

El número total de aristas en el árbol es el número de Nodes menos 1, es decir, |E| = L + YO – 1. 

Todos los Nodes internos excepto root en el tipo de árbol dado tienen grado k + 1. Root tiene un grado k. Todas las hojas tienen grado 1. Aplicando el lema Handshaking a tales árboles, obtenemos la siguiente relación. 

  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   

Entonces, la propiedad anterior se demuestra usando Handshaking Lemma, discutamos una propiedad más interesante. 

Prueba alternativa: (sin usar el teorema del apretón de manos):

Dado que hay I Nodes internos, cada uno con K hijos, por lo tanto, el total de hijos en el árbol = K * I. 
Hay I-1 Nodes internos que son hijos de algún otro Node (la raíz se ha excluido, por lo tanto, uno menos que el número total de Nodes). Nodes internos) 
Es decir, de estos hijos K*I, I-1 son Nodes internos y por lo tanto el resto (K*I – (I-1)) son hojas. 
Por lo tanto L = (K-1)*I + 1. 

2) En un árbol binario, el número de Nodes hoja siempre es uno más que los Nodes con dos hijos. 

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

Prueba: 

Deje que un número de Nodes con 2 hijos sea T. La prueba se puede dividir en tres casos. 

Caso 1: Solo hay un Node, la relación se mantiene 
como T = 0, L = 1. 

Caso 2: La raíz tiene dos hijos, es decir, el grado de la raíz es 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 

Caso 3: La raíz tiene un hijo, es decir, el grado de la raíz es 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 

Por lo tanto, en los tres casos, obtenemos T = L-1. 

Hemos discutido la prueba de dos propiedades importantes de los árboles usando Handshaking Lemma. Se han hecho muchas preguntas GATE sobre estas propiedades, los siguientes son algunos enlaces. 

GATE-CS-2015 (Conjunto 3) | Pregunta 35  
GATE-CS-2015 (Conjunto 2) | Pregunta 20  
GATE-CS-2005 | Pregunta 36  
GATE-CS-2002 | Pregunta 34  
GATE-CS-2007 | Pregunta 43