Número de árboles de expansión de un gráfico completo ponderado

Prerrequisitos: Conceptos básicos de teoría de grafos, árbol de expansión.

Gráfico ponderado completo: un gráfico en el que un borde conecta cada par de vértices del gráfico y cada borde tiene un peso asociado se conoce como gráfico ponderado completo. 

El número de árboles de expansión para un gráfico ponderado completo con n vértices es n ^(n-2) .

Prueba: El árbol de expansión es el subgrafo del grafo G que contiene todos los vértices del grafo. Por lo tanto, el número de árboles de expansión de un gráfico ponderado completo es el mismo que el número de árboles etiquetados (no es necesario que sean binarios) con n vértices.

La secuencia de Prüfer de un árbol etiquetado de n vértices es una secuencia única de longitud (n-2) asociada con el árbol. Además, para una secuencia de Prüfer dada de longitud (n-2) en las etiquetas 1 a n, hay un árbol etiquetado único con la secuencia de Prüfer dada. Por lo tanto, tenemos una biyección entre el conjunto A de árboles etiquetados con n vértices y el conjunto B de secuencias de Prüfer de tamaño n-2 en las etiquetas 1 a n . Esto se puede probar de la siguiente manera –

Sea T un árbol etiquetado con vértices 1,2,…,n, y S como una secuencia de Prüfer de tamaño (n-2). Así, T y S son los elementos de los conjuntos A y B, respectivamente.

(i) Árbol etiquetado (T) –> Secuencia de Prufer (S)

Construyendo la secuencia de Prüfer de un árbol etiquetado – 

Inicialmente, sea S = NULL.

Procedimiento –

• Encuentre el Node hoja (L) de T con la etiqueta más pequeña.
• Agregue el vecino de L a S.
• Elimine el Node hoja, L.
• Repita los pasos anteriores hasta que solo queden dos Nodes en el árbol (solo es posible un árbol de expansión).
• Construimos la secuencia de Prüfer S asociada con el árbol etiquetado T.

Observaciones –

• Ningún Node hoja se adjunta a S.
• Cada vértice V del árbol T se suma a S, un total de grado(V)-1 veces.
• El árbol T tiene n vértices y por lo tanto (n-1) aristas.
• Número de términos en S = Suma de (grado(V) – 1) para todos los vértices V pertenecientes al árbol T = Suma de grado de todos los vértices del árbol T – (1+1+…+1..n veces) = 2(nº de aristas) – n = 2*(n-1) – n = n-2. (Ya que la suma del grado de todos los vértices de un árbol = 2*nº de aristas del árbol).
• Por lo tanto, T es análoga a la secuencia S de Prüfer de longitud (n-2).

(ii) Secuencia de Prufer (S) –> Árbol etiquetado (T)

Construyendo el árbol etiquetado a partir de su secuencia Pr ü fer –

Procedimiento-

• Sea L = {1, 2, …, n} el conjunto de etiquetas (vértices de T).
• Sea S = {a ₁ ,a ₂ ,…,a _(n-2) } la sucesión de Prüfer de tamaño (n-2) donde cada a _i pertenece a L.
• Encuentre el elemento x más pequeño que pertenece a L pero no está en S.
• Conecte x y el primer elemento de S (a ₁ ) a través de un borde.
• Eliminar un ₁ de S, x de L (Así, S:=S-{a ₁ } y, L:=L-{x}).
• De manera similar, encuentre y, el elemento más pequeño que pertenece a L y no a S.
• Conecte y y el primer elemento de S(a ₂ ).
• Retire y de L y a ₂ de S (Así, S:=S-{a ₂ } y, L:=L-{y}).
• Continúe el proceso anterior hasta que queden dos elementos en L.
• Conecte estos dos elementos en el árbol formado hasta ahora.

El árbol obtenido de S es el mismo que T. Por lo tanto, la secuencia de Prüfer S de tamaño (n-2) es análoga a T (S <–> T). Por lo tanto, existe una biyección entre el conjunto de árboles etiquetados con n vértices y el conjunto de secuencias de Prüfer de tamaño (n-2) en las etiquetas 1 a n.

Por lo tanto, el número de árboles de expansión de un gráfico ponderado completo de n vértices = número de árboles etiquetados con n vértices = número de secuencias de Prüfer de tamaño (n-2) = n ^(n-2) .