En matemática combinatoria , la secuencia de Prüfer (también código de Prüfer o números de Prüfer ) de un árbol etiquetado es una secuencia única asociada con el árbol. La secuencia de un árbol en n vértices tiene una longitud n - 2 y se puede generar mediante un algoritmo iterativo simple. Las secuencias de Prüfer fueron utilizadas por primera vez por Heinz Prüfer para probar la fórmula de Cayley en 1918. [1]
Algoritmo para convertir un árbol en una secuencia de Prüfer
Se puede generar la secuencia Prüfer de un árbol etiquetado eliminando iterativamente los vértices del árbol hasta que solo queden dos vértices. Específicamente, considere un árbol etiquetado T con vértices {1, 2, ..., n }. En el paso i , retire la hoja con la etiqueta más pequeña y configure el i- ésimo elemento de la secuencia de Prüfer para que sea la etiqueta de la vecina de esta hoja.
La secuencia de Prüfer de un árbol etiquetado es única y tiene una longitud n - 2.
Tanto la codificación como la decodificación se pueden reducir a la clasificación de base entera y paralelizar. [2]
Ejemplo
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/24/Tree_graph.svg/162px-Tree_graph.svg.png)
Considere el algoritmo anterior ejecutado en el á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 quita primero y el 4 se coloca en la secuencia de Prüfer. Los vértices 2 y 3 se eliminan a continuación, por lo que 4 se agrega dos veces más. El vértice 4 ahora es una hoja y tiene la etiqueta más pequeña, por lo que se quita y agregamos 5 a la secuencia. Nos quedan solo dos vértices, así que nos detenemos. La secuencia del árbol es {4,4,4,5}.
Algoritmo para convertir una secuencia de Prüfer en un árbol
Sea {a[1], a[2], ..., a[n]}
una secuencia de Prüfer:
El árbol tendrá n+2
nodos, numerados del 1
a n+2
. Para cada nodo, establezca su grado según la cantidad de veces que aparece en la secuencia más 1. Por ejemplo, en pseudocódigo:
Convertir Prüfer en árbol ( a ) 1 n ← longitud [ a ] 2 T ← un gráfico con n + 2 nodos aislados, numerados del 1 al n + 2 3 grados ← una matriz de números enteros 4 para cada nodo i en T hacer 5 grados [ i ] ← 1 6 por cada valor i en un do 7 grado [ i ] ← grado [ i ] + 1
A continuación, para cada número de la secuencia a[i]
, busque el primer nodo (con el número más bajo) j
, con un grado igual a 1, agregue el borde (j, a[i])
al árbol y disminuya los grados de j
y a[i]
. En pseudocódigo:
8 para cada valor i en a do 9 para cada nodo j en T do 10 si grado [ j ] = 1 entonces 11 Inserte el borde [ i , j ] en T 12 grados [ i ] ← grado [ i ] - 113 grados [ j ] ← grado [ j ] - 114 descanso
Al final de este bucle quedarán dos nodos con grado 1 (llámalos u
, v
). Por último, agregue el borde (u,v)
al árbol. [3]
15 u ← v ← 016 para cada nodo i en T 17 si grado [ i ] = 1 entonces 18 si u = 0 entonces 19 u ← i 20 más 21 v ← i 22 romper 23 Insertar borde [ u , v ] en T 24 grados [ u ] ← grado [ u ] - 125 grados [ v ] ← grado [ v ] - 126 volver T
Fórmula de Cayley
La secuencia de Prüfer de un árbol etiquetado en n vértices es una secuencia única de longitud n - 2 en las etiquetas 1 an . Para una determinada secuencia S de longitud n -2 en las etiquetas 1 a n , hay un único árbol de marcado 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 en n vértices y el conjunto de secuencias de longitud n - 2 en las etiquetas 1 an . El último conjunto tiene un tamaño n n -2 , por lo que la existencia de esta biyección prueba la fórmula de Cayley , es decir, que hay n n -2 árboles etiquetados en n vértices.
Otras aplicaciones [4]
- La fórmula de Cayley se puede fortalecer para probar la siguiente afirmación:
- El número de árboles de expansión en un gráfico completo con un grado especificado para cada vértice es igual al coeficiente multinomial
- La prueba sigue al observar que en el número de secuencia de Prüfer aparece exactamente veces.
- La fórmula de Cayley se puede generalizar: un árbol etiquetado es de hecho un árbol de expansión del gráfico 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 gráfico bipartito completo . Si G es el gráfico bipartito completo con vértices 1 an 1 en una partición y vértices n 1 + 1 an en la otra partición, el número de árboles de expansión etiquetados de G es, donde n 2 = n - n 1 .
- Generar secuencias Prüfer aleatorias distribuidas uniformemente y convertirlas en los árboles correspondientes es un método sencillo de generar árboles etiquetados aleatorios distribuidos uniformemente.
Referencias
- ^ Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arco. Matemáticas. Phys . 27 : 742–744.
- ^ Caminiti, S., Finocchi, I., Petreschi, R. (2007). "Sobre la codificación de árboles etiquetados". Informática Teórica . 382 (2): 97–108. doi : 10.1016 / j.tcs.2007.03.009 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Jens Gottlieb; Bryant A. Julstrom; Günther R. Raidl; Franz Rothlauf. (2001). "Números de Prüfer: una mala representación de árboles de expansión para la búsqueda evolutiva" (PDF) . Actas de la Conferencia de Computación Genética y Evolutiva (GECCO-2001) : 343–350. Archivado desde el original (PDF) el 26 de septiembre de 2006.
- ^ Kajimoto, H. (2003). "Una extensión del código Prüfer y ensamblaje de gráficos conectados de sus bloques". Gráficos y Combinatoria . 19 : 231-239. doi : 10.1007 / s00373-002-0499-3 .
enlaces externos
- Código Prüfer - de MathWorld