Secuencia de Prüfer

En matemáticas combinatorias , la secuencia de Prüfer (también llamada código de Prüfer o números de Prüfer ) de un árbol etiquetado es una secuencia única asociada a dicho árbol. La secuencia para un árbol con n vértices tiene una longitud de n − 2 y puede generarse mediante un algoritmo iterativo sencillo. Heinz Prüfer utilizó por primera vez las secuencias de Prüfer para demostrar la fórmula de Cayley en 1918. ^{[ 1 ]}

Se puede generar la secuencia de Prüfer de un árbol etiquetado eliminando iterativamente vértices hasta que solo queden dos. Específicamente, consideremos un árbol etiquetado T con vértices {1, 2, ..., n } . En el paso i , se elimina la hoja con la etiqueta más pequeña y se asigna al i -ésimo elemento de la secuencia de Prüfer la etiqueta de la hoja vecina.

La secuencia de Prüfer de un árbol etiquetado es única y tiene una longitud de n − 2 .

Tanto la codificación como la decodificación pueden reducirse a una ordenación por radix de enteros y paralelizarse. ^{[ 2 ]}

Ejemplo

Consideremos el algoritmo anterior aplicado al árbol que se muestra a la derecha. Inicialmente, el vértice 1 es la hoja con la etiqueta más pequeña, por lo que se elimina primero y se añade el 4 a la secuencia de Prüfer. A continuación, se eliminan los vértices 2 y 3, por lo que se añade el 4 dos veces más. El vértice 4 ahora es una hoja y tiene la etiqueta más pequeña, por lo que se elimina y se añade el 5 a la secuencia. Nos quedan solo dos vértices, así que finalizamos el proceso. La secuencia del árbol es [4,4,4,5].

Sea [a[1], a[2], ..., a[n]]una sucesión de Prüfer:

El árbol tendrá n+2nodos, numerados del 11 al 2. n+2Para cada nodo, su grado se establece como el número de veces que aparece en la secuencia más 1. Por ejemplo, en pseudocódigo:

Convertir-Prüfer-a-Árbol ( a ) 1 n ← longitud [ a ] 2 T ← un grafo con n + 2 nodos aislados, numerados del 1 al n + 2 3er grado ← una matriz de enteros 4 para cada nodo i en T hacer 5 grado [ i ] ← 1 6 para cada valor i en a hacer 7 grado [ i ] ← grado [ i ] + 1

A continuación, para cada número de la secuencia a[i], encuentra el primer nodo (el de menor número), j, con grado igual a 1, agrega la arista (j, a[i])al árbol y decrementa los grados de jy a[i]. En pseudocódigo:

8 para cada valor i en a hacer 9 para cada nodo j en T hacer 10 si grado [ j ] = 1 entonces 11 Insertar arista [ i , j ] en T 12 grado [ i ] ← grado [ i ] - 1 13 grados [ j ] ← grados [ j ] - 1 14 descanso

Al final de este bucle quedarán dos nodos con grado 1 (llamémoslos u, v). Por último, agregue la arista (u,v)al árbol. ^{[ 3 ]}

15 u ← v ← 0 16 para cada nodo i en T 17 si grado [ i ] = 1 entonces 18 si u = 0 entonces 19 u ← i 20 sino 21 v ← i 22 romper 23 Insertar arista [ u , v ] en T 24 grado [ u ] ← grado [ u ] - 1 25 grados [ v ] ← grados [ v ] - 1 26 regreso T

La secuencia de Prüfer de un árbol etiquetado con n vértices es una secuencia única de longitud n − 2 en las etiquetas del 1 al n . Para una secuencia S dada de longitud n − 2 en las etiquetas del 1 al n , existe un árbol etiquetado único cuya secuencia de Prüfer es S.   

La consecuencia inmediata es que las secuencias de Prüfer proporcionan una biyección entre el conjunto de árboles etiquetados con n vértices y el conjunto de secuencias de longitud n − 2 con etiquetas del 1 al n . Este último conjunto tiene un tamaño de n ^{n − 2} , por lo que la existencia de esta biyección demuestra la fórmula de Cayley , es decir, que hay n ^{n − 2} árboles etiquetados con n vértices.

Fuente: ^{[ 4 ]}

• La fórmula de Cayley puede reforzarse para demostrar la siguiente afirmación:

El número de árboles de expansión en un grafo completo${\displaystyle K_{n}}$con un título${\displaystyle d_{i}}$especificado para cada vértice${\displaystyle i}$es igual al coeficiente multinomial

${\displaystyle {\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.}$

La demostración se deduce al observar que en la secuencia de Prüfer número${\displaystyle i}$aparece exactamente${\textstyle d_{i}-1}$veces.

• La fórmula de Cayley se puede generalizar: un árbol etiquetado es, de hecho, un árbol de expansión del grafo completo etiquetado . Al imponer restricciones a las secuencias de Prüfer enumeradas, métodos similares pueden dar el número de árboles de expansión de un grafo bipartito completo . Si G es el grafo bipartito completo con vértices del 1 al n ₁ en una partición y vértices del n ₁ + 1 al n en la otra partición, el número de árboles de expansión etiquetados de G es${\ Displaystyle n_ {1} ^ {n_ {2} -1} n_ {2} ^ {n_ {1} -1}}$, donde n ₂ = n − n ₁ .
• Generar secuencias de Prüfer aleatorias con distribución uniforme y convertirlas en los árboles correspondientes es un método sencillo para generar árboles etiquetados aleatorios con distribución uniforme.

• Código Prüfer – de MathWorld