Codigo purfer

El código de Prufer asigna a un árbol finito arbitrario con vértices una secuencia de números (de a ) con posibles repeticiones. La relación entre un árbol con vértices etiquetados y un código Prufer es de uno a uno: cada árbol corresponde a un código Prufer único y los elementos de la secuencia del código están asociados con los números de vértice. Por el contrario, un árbol con vértices se puede restaurar de forma única a partir de un código dado de números . El código fue construido por Heinz Prüfer mientras probaba la fórmula de Cayley en 1918. [una] $norte$ $n-2$ $una$ $norte$ $n-2$ $norte$

Edificio

Sea un árbol con vértices numerados por números . La construcción del código de Prufer del árbol T se lleva a cabo eliminando secuencialmente vértices del árbol hasta que solo quedan dos vértices. En este caso, cada vez que se selecciona el vértice final con el número más pequeño, se escribe en el código el número del único vértice con el que está conectado. El resultado es una secuencia formada por números , posiblemente con repeticiones. $T$ $\{1,2,\puntos,n\}$ ${\ estilo de visualización (p_ {1}, \ puntos, p_ {n-2})}$ $\{1,2,\puntos,n\}$

Ejemplo

Para el árbol del diagrama, el vértice 1 es el vértice terminal con el número más bajo, por lo que se elimina primero y se escribe 4 en el código Prufer.

Los vértices 2 y 3 se eliminan a continuación, por lo que se agrega 4 dos veces al código.

El vértice 4 es ahora el nodo terminal y tiene el número más bajo, por lo que se elimina y se agrega 5 al código.

Solo quedan dos vértices, por lo que el código se escribe en su totalidad y el proceso se detiene.

El resultado es un código Prufer (4,4,4,5).

Restauración de árboles

Para restaurar el árbol por código, preparemos una lista de números de vértice . Elijamos el primer número , que no se encuentra en el código. Agregue un borde , luego elimine desde y desde . $p=(p_{1},\puntos,p_{n-2})$ ${\ estilo de visualización s = (1, \ puntos, n)}$ $i_1$ ${\ estilo de visualización (i_ {1}, p_ {1})}$ $i_1$ $s$ $p_{1}$ $pags$

Repetimos el proceso hasta que el código quede vacío. En este punto, la lista contiene exactamente dos números y . Queda por agregar un borde , y el árbol está construido. $pags$ $s$ ${\ estilo de visualización i_ {n-1}}$ $norte$ ${\ estilo de visualización (i_ {n-1}, n)}$

Propiedades

Si es el grado del vértice con número , entonces ocurre exactamente ( ) veces en el código de Prufer . $d_{i}$ $i$ $i$ ${\ estilo de visualización d_ {i} -1}$

Aplicaciones

La fórmula de Cayley se deriva del código de Prufer , es decir, el número de árboles de expansión de un grafo completo con vértices es igual a . La prueba se deriva del hecho de que el código de Prufer da una biyección entre árboles de expansión y secuencias de longitud de números. $\Alfiler}$ $norte$ $n^{{n-2}}$ $n-2$ $norte$
El código de Prufer también permite generalizar la fórmula de Cayley al caso cuando se dan grados de vértices, si es una secuencia de grados de un árbol, entonces el número de árboles con tales grados es igual al coeficiente multinominal ${\ estilo de visualización (d_ {1}, \ puntos, d_ {n})}$

{\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)!}}.

El código Prufer se usa para construir árboles aleatorios.

Enlaces

↑ Prüfer, H. Neuer Beweis eines Satzes über Permutationen (alemán) // Arch. Matemáticas. Phys.. - 1918. - Bd. 27 . - S. 742-744 .