Secuencia de Prüfer

En matemáticas combinatorias , 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 para un árbol en n vértices tiene una longitud de 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 demostrar la fórmula de Cayley en 1918. ^[1]

Algoritmo para convertir un árbol en una secuencia de Prüfer

Se puede generar una secuencia de Prüfer de un árbol etiquetado eliminando iterativamente vértices del árbol hasta que solo queden dos. En concreto, considere un árbol etiquetado T con vértices {1, 2, ..., n }. En el paso i , elimine la hoja con la etiqueta más pequeña y establezca el elemento i de la secuencia de Prüfer como la etiqueta del vecino de esta hoja.

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

Tanto la codificación como la decodificación pueden reducirse a una clasificación por radio de números enteros y paralelizarse. ^[2]

Ejemplo

Un árbol etiquetado con secuencia de Prüfer {4,4,4,5}.

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 elimina primero y se coloca 4 en la secuencia de Prüfer. Los vértices 2 y 3 se eliminan a continuación, por lo que se agrega 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 agregamos 5 a la secuencia. Nos quedan solo dos vértices, por lo 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+2nodos, numerados del 1a n+2. Para cada nodo, establezca su grado en 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 (de menor número), j, con grado igual a 1, agregue la arista (j, a[i])al árbol y disminuya los grados de jy a[i]. En pseudocódigo:

8 para cada valor i en a  haz 9 para cada nodo j en T  haz
10 si  grado [ j ] = 1 entonces
11 Inserta borde [ i , j ] en T
12 grado [ i ] ← grado [ i ] - 113 grado [ j ] ← grado [ j ] - 114 descanso

Al final de este bucle quedarán dos nodos de grado 1 (los llamaremos u, v). Por último, añadiremos la arista (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 de lo contrario
21 v ← i
22 ruptura
23 Insertar borde [ u , v ] en T
24 grado [ u ] ← grado [ u ] - 125 grados [ v ] ← grados [ v ] - 126 retorno  T

La 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 a  n . Para una secuencia dada S de longitud n  − 2 en las etiquetas 1 a  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 en n vértices y el conjunto de secuencias de longitud n  − 2 en las etiquetas 1 a n . El último conjunto tiene 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 demostrar 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 ${\displaystyle K_{n}}$ ${\displaystyle d_{i}}$ ${\displaystyle i}$

${\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 prueba se obtiene observando que en la secuencia de Prüfer el número aparece exactamente veces. ${\displaystyle i}$ ${\textstyle d_{i}-1}$

• La fórmula de Cayley se puede generalizar: un árbol etiquetado es, de hecho, un árbol de expansión del grafo completo etiquetado . Al poner restricciones en 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 1 a n ₁ en una partición y vértices n ₁  + 1 a n en la otra partición, el número de árboles de expansión etiquetados de G es , donde n ₂ = n  −  n ₁ . ${\displaystyle n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}}$
• Generar secuencias de Prüfer aleatorias distribuidas uniformemente y convertirlas en los árboles correspondientes es un método sencillo para generar árboles etiquetados aleatorios distribuidos uniformemente.

Referencias

1. Prufer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arco. Matemáticas. Física . 27 : 742–744.
2. Caminiti, S., Finocchi, I., Petreschi, R. (2007). "Sobre la codificación de árboles etiquetados". Ciencias de la Computación Teórica . 382 (2): 97–108. doi : 10.1016/j.tcs.2007.03.009 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
3. Jens Gottlieb; Bryant A. Julstrom; Günther R. Raidl; Franz Rothlauf. (2001). "Números de Prüfer: una pobre representación de árboles de expansión para la búsqueda evolutiva" (PDF) . Actas de la Conferencia sobre Computación Genética y Evolutiva (GECCO-2001) : 343–350. Archivado desde el original (PDF) el 26 de septiembre de 2006.
4. Kajimoto, H. (2003). "Una extensión del código de Prüfer y ensamblaje de grafos conectados a partir de sus bloques". Graphs and Combinatorics . 19 (2): 231–239. doi :10.1007/s00373-002-0499-3. S2CID  22970936.

Enlaces externos

• Código Prüfer – de MathWorld