Fórmula de Cayley

Fórmula de Cayley : esta fórmula indica cuántos árboles se pueden construir con N vértices. Indica que hay N ^{N – 2}   árboles etiquetados de N Nodes. Los Nodes se etiquetan de 1, 2, …, N , y dos árboles son diferentes si su estructura o etiquetado es diferente.

Por ejemplo: cuando N es 4 , el número de árboles etiquetados es 4 ^{4 – 2} = 16.

A continuación se muestra la imagen que muestra el número de árboles etiquetados:

En la imagen de arriba, se dan 4 Nodes a partir de los cuales se crean 16 árboles etiquetados .

Fórmula de Cayley derivada usando códigos de Prüfer :

Código Prüfer :

• Un Código Prüfer es una secuencia de (N – 2) números que describen un árbol etiquetado.
• El código se construye siguiendo un proceso que elimina (N – 2) hojas del árbol.
• En cada paso, se elimina la hoja con la etiqueta más pequeña y se agrega al código la etiqueta de su único vecino.

A continuación se detallan los pasos para calcular el Código Prüfer del siguiente gráfico :

• Dado un gráfico con cinco Nodes:

• Elimine el Node 1 y agregue el Node 4 al código:

• Luego elimine el Node 3 y agregue el Node 4 al código:

• Finalmente, elimine el Node 4 y agregue el Node 2 al código:

Por lo tanto, el código de Prüfer del gráfico viene dado por {4, 4, 2} .

• El código Prüfer se puede construir para cualquier árbol.
• El árbol original se puede reconstruir a partir de un código Prüfer.
• Por lo tanto, el número de árboles etiquetados de n Nodes es igual a N ^{N – 2} , el número de códigos Prüfer de tamaño N.