La siguiente relación se cumple en cualquier árbol n-ario en el que cada Node tenga 0 o n hijos.
L = (n-1)*I + 1
Donde L es el número de Nodes hoja e I es el número de Nodes internos.
Prueba:
El árbol es un árbol n-ario. Suponga que tiene T Nodes totales, que es la suma de los Nodes internos (I) y los Nodes de hoja (L). Un árbol con T Nodes totales tendrá (T – 1) aristas o ramas.
En otras palabras, dado que el árbol es un árbol n-ario, cada Node interno tendrá n ramas que contribuirán en total a n*I ramas internas. Por lo tanto tenemos las siguientes relaciones de las explicaciones anteriores,
n*I = T – 1
L + I = T
A partir de las dos ecuaciones anteriores, es fácil demostrar que L = (n – 1) * I + 1.
Gracias a venki por proporcionar la prueba.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA