Almacenamiento de repuestos de un árbol

Question

Me puede almacenar cualquier grafo simple gráfico N vértices usando $b = (N-1)N/2$ bits, mediante la creación de una máscara de los bordes en la parte superior de la diagonal de la matriz de adyacencia. Por ejemplo, la matriz de adyacencia de $K_3$ es

$$ Un = [[0,1,1],[1,0,1],[1,1,0]] $$

la cual puede ser almacenada como la máscara de bits $011101110$ o como un número entero en base 10 como $238$. En general, este número no es el único (debido a gráfico isomorphisms) pero no importa para mis propósitos. Desde un punto de vista práctico, esto significa que se puede almacenar gráficos a a $N=11$ en una base de datos utilizando un entero de 64 bits.

Mi pregunta ahora involucra a los árboles, que son considerablemente más borde dispersas. Hay un esquema de asignación de la que puede permitir a mí a la tienda (y rápidamente reconstruir), los árboles, $N>11$ mediante el uso de un único entero de 64 bits?

Answer 1

El número de árboles de expansión en el gráfico de $n$ vértices es $n^{n-2}$, Una forma común de dirección de un árbol es a través de su código de Prüfer.

Si queremos hablar acerca de los árboles que no pueden ser árboles de expansión podríamos dirección de este problema por primera asignar el conjunto de vértices del árbol y, a continuación, dando su código de Prüfer.

De todos modos no es posible almacenar cada árbol en $n$ vértices utilizando un $64$-bit intger debido a que el número de estos árboles es más que $n^{n-2}$ $n^{n-2}$ es stricty mayor que $2^{64}$ $n\geq 18$