Código de Prüfer

En este artículo veremos el llamado código de Prüfer (o secuencia de Prüfer), que es una forma de codificar un árbol etiquetado en una secuencia de números de manera única.

Con ayuda del código de Prüfer demostraremos la fórmula de Cayley (que especifica el número de árboles de expansión en un grafo completo). También mostramos la solución al problema de contar el número de formas de agregar aristas a un grafo para hacerlo conexo.

Nota: no consideraremos árboles que consisten de un solo vértice: este es un caso especial en el que varias afirmaciones entran en conflicto.

Código de Prüfer

El código de Prüfer es una forma de codificar un árbol etiquetado con $n$ vértices usando una secuencia de $n - 2$ enteros en el intervalo $[0; n-1]$. Esta codificación también actúa como una biyección entre todos los árboles de expansión de un grafo completo y las secuencias numéricas.

Aunque usar el código de Prüfer para almacenar y operar sobre un árbol es poco práctico debido a las peculiaridades de la representación, los códigos de Prüfer se usan con frecuencia: sobre todo para resolver problemas combinatorios.

El inventor — Heinz Prüfer — propuso este código en 1918 como una demostración de la fórmula de Cayley.

Construcción del código de Prüfer de un árbol dado

El código de Prüfer se construye de la siguiente forma. Repetiremos el siguiente procedimiento $n - 2$ veces: seleccionamos la hoja del árbol con el número más pequeño, la quitamos del árbol, y escribimos el número del vértice que estaba conectado a ella. Después de $n - 2$ iteraciones solo quedarán $2$ vértices, y el algoritmo termina.

Así, el código de Prüfer de un árbol dado es una secuencia de $n - 2$ números, donde cada número es el número del vértice conectado, es decir, este número está en el intervalo $[0, n-1]$.

El algoritmo para calcular el código de Prüfer se puede implementar fácilmente con complejidad temporal $O(n \log n)$, simplemente usando una estructura de datos para extraer el mínimo (por ejemplo set o priority_queue en C++), que contiene una lista de todas las hojas actuales.

vector<vector<int>> adj;

vector<int> pruefer_code() {
    int n = adj.size();
    set<int> leafs;
    vector<int> degree(n);
    vector<bool> killed(n, false);
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] == 1)
            leafs.insert(i);
    }

    vector<int> code(n - 2);
    for (int i = 0; i < n - 2; i++) {
        int leaf = *leafs.begin();
        leafs.erase(leafs.begin());
        killed[leaf] = true;

        int v;
        for (int u : adj[leaf]) {
            if (!killed[u])
                v = u;
        }

        code[i] = v;
        if (--degree[v] == 1)
            leafs.insert(v);
    }

    return code;
}

Sin embargo, la construcción también se puede implementar en tiempo lineal. Tal enfoque se describe en la siguiente sección.

Construcción del código de Prüfer de un árbol dado en tiempo lineal

La esencia del algoritmo es usar un puntero móvil, que siempre apuntará a la hoja actual que queremos quitar.

A primera vista esto parece imposible, porque durante el proceso de construcción del código de Prüfer el número de hoja puede aumentar y disminuir. Sin embargo, tras una mirada más atenta, en realidad no es así. El número de hojas no aumentará. O bien el número disminuye en uno (quitamos una hoja y no ganamos una nueva), o bien se mantiene igual (quitamos una hoja y ganamos otra). En el primer caso no hay otra forma que buscar la siguiente hoja más pequeña. En el segundo caso, sin embargo, podemos decidir en tiempo $O(1)$ si podemos continuar usando el vértice que se convirtió en una hoja nueva, o si tenemos que buscar la siguiente hoja más pequeña. Y en bastantes ocasiones podemos continuar con la hoja nueva.

Para ello usaremos una variable $\text{ptr}$, que indicará que en el conjunto de vértices entre $0$ y $\text{ptr}$ hay a lo sumo una hoja, a saber la actual. Todos los demás vértices en ese rango o bien ya se quitaron del árbol, o bien todavía tienen más de un vértice adyacente. Al mismo tiempo decimos que aún no hemos quitado ninguna hoja mayor que $\text{ptr}$.

Esta variable ya es muy útil en el primer caso. Después de quitar la hoja actual, sabemos que no puede haber una hoja entre $0$ y $\text{ptr}$, por tanto podemos empezar la búsqueda de la siguiente directamente en $\text{ptr} + 1$, y no tenemos que empezar la búsqueda de nuevo en el vértice $0$. Y en el segundo caso, podemos distinguir además dos casos: O bien la hoja recién obtenida es menor que $\text{ptr}$, entonces esta debe ser la siguiente hoja, ya que sabemos que no hay otros vértices menores que $\text{ptr}$. O bien la hoja recién obtenida es mayor. Pero entonces también sabemos que tiene que ser mayor que $\text{ptr}$, y podemos empezar la búsqueda de nuevo en $\text{ptr} + 1$.

Aunque podamos tener que realizar varias búsquedas lineales de la siguiente hoja, el puntero $\text{ptr}$ solo aumenta y por tanto la complejidad temporal total es $O(n)$.

vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
    for (int u : adj[v]) {
        if (u != parent[v]) {
            parent[u] = v;
            dfs(u);
        }
    }
}

vector<int> pruefer_code() {
    int n = adj.size();
    parent.resize(n);
    parent[n-1] = -1;
    dfs(n-1);

    int ptr = -1;
    vector<int> degree(n);
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] == 1 && ptr == -1)
            ptr = i;
    }

    vector<int> code(n - 2);
    int leaf = ptr;
    for (int i = 0; i < n - 2; i++) {
        int next = parent[leaf];
        code[i] = next;
        if (--degree[next] == 1 && next < ptr) {
            leaf = next;
        } else {
            ptr++;
            while (degree[ptr] != 1)
                ptr++;
            leaf = ptr;
        }
    }

    return code;
}

En el código primero encontramos para cada vértice su ancestro parent[i], es decir, el ancestro que este vértice tendrá una vez que lo quitemos del árbol. Podemos encontrar este ancestro enraizando el árbol en el vértice $n-1$. Esto es posible porque el vértice $n-1$ nunca se quitará del árbol. También calculamos el grado de cada vértice. ptr es el puntero que indica el tamaño mínimo de las hojas restantes (excepto la actual leaf). O bien asignaremos la hoja actual con next, si esta también es una hoja y es menor que ptr, o bien empezamos una búsqueda lineal de la hoja más pequeña incrementando el puntero.

Se ve fácilmente que este código tiene complejidad $O(n)$.

Algunas propiedades del código de Prüfer

• Después de construir el código de Prüfer quedarán dos vértices. Uno de ellos es el vértice de mayor índice $n-1$, pero no se puede decir nada más sobre el otro.
• Cada vértice aparece en el código de Prüfer exactamente un número fijo de veces: su grado menos uno. Esto se puede comprobar fácilmente, ya que el grado se reduce cada vez que registramos su etiqueta en el código, y lo quitamos una vez que el grado es $1$. Para los dos vértices restantes este hecho también es cierto.

Restaurar el árbol a partir del código de Prüfer

Para restaurar el árbol basta con centrarse solo en la propiedad discutida en la sección anterior. Ya conocemos el grado de todos los vértices del árbol deseado. Por tanto podemos encontrar todas las hojas, y también la primera hoja que se quitó en el primer paso (tiene que ser la hoja más pequeña). Esta hoja estaba conectada al vértice correspondiente al número de la primera celda del código de Prüfer.

Así encontramos la primera arista que se quitó cuando se generó el código de Prüfer. Podemos agregar esta arista a la respuesta y reducir los grados en ambos extremos de la arista.

Repetiremos esta operación hasta haber usado todos los números del código de Prüfer: buscamos el vértice mínimo con grado igual a $1$, lo conectamos con el siguiente vértice del código de Prüfer, y reducimos el grado.

Al final solo nos quedan dos vértices con grado igual a $1$. Estos son los vértices que no se quitaron en el proceso del código de Prüfer. Los conectamos para obtener la última arista del árbol. Uno de ellos siempre será el vértice $n-1$.

Este algoritmo se puede implementar fácilmente en $O(n \log n)$: usamos una estructura de datos que soporta extraer el mínimo (por ejemplo set<> o priority_queue<> en C++) para guardar todas las hojas.

La siguiente implementación devuelve la lista de aristas correspondiente al árbol.

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
    int n = code.size() + 2;
    vector<int> degree(n, 1);
    for (int i : code)
        degree[i]++;

    set<int> leaves;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1)
            leaves.insert(i);
    }

    vector<pair<int, int>> edges;
    for (int v : code) {
        int leaf = *leaves.begin();
        leaves.erase(leaves.begin());

        edges.emplace_back(leaf, v);
        if (--degree[v] == 1)
            leaves.insert(v);
    }
    edges.emplace_back(*leaves.begin(), n-1);
    return edges;
}

Restaurar el árbol a partir del código de Prüfer en tiempo lineal

Para obtener el árbol en tiempo lineal podemos aplicar la misma técnica usada para obtener el código de Prüfer en tiempo lineal.

No necesitamos una estructura de datos para extraer el mínimo. En su lugar podemos observar que, después de procesar la arista actual, solo un vértice se convierte en hoja. Por tanto podemos o bien continuar con este vértice, o bien encontrar uno más pequeño con una búsqueda lineal moviendo un puntero.

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
    int n = code.size() + 2;
    vector<int> degree(n, 1);
    for (int i : code)
        degree[i]++;

    int ptr = 0;
    while (degree[ptr] != 1)
        ptr++;
    int leaf = ptr;

    vector<pair<int, int>> edges;
    for (int v : code) {
        edges.emplace_back(leaf, v);
        if (--degree[v] == 1 && v < ptr) {
            leaf = v;
        } else {
            ptr++;
            while (degree[ptr] != 1)
                ptr++;
            leaf = ptr;
        }
    }
    edges.emplace_back(leaf, n-1);
    return edges;
}

Biyección entre árboles y códigos de Prüfer

Para cada árbol existe un código de Prüfer que le corresponde. Y para cada código de Prüfer podemos restaurar el árbol original.

Se sigue que también todo código de Prüfer (es decir, una secuencia de $n-2$ números en el rango $[0; n - 1]$) corresponde a un árbol.

Por tanto todos los árboles y todos los códigos de Prüfer forman una biyección (una correspondencia uno a uno).

Fórmula de Cayley

La fórmula de Cayley afirma que el número de árboles de expansión en un grafo completo etiquetado con $n$ vértices es igual a:

$$n^{n-2}$$

Hay varias demostraciones de esta fórmula. Usando el concepto de código de Prüfer esta afirmación no sorprende.

De hecho, cualquier código de Prüfer con $n-2$ números del intervalo $[0; n-1]$ corresponde a algún árbol con $n$ vértices. Así que tenemos $n^{n-2}$ códigos de Prüfer distintos de ese tipo. Como cada uno de esos árboles es un árbol de expansión de un grafo completo con $n$ vértices, el número de tales árboles de expansión también es $n^{n-2}$.

Número de formas de hacer conexo un grafo

El concepto de códigos de Prüfer es aún más potente. Permite crear muchas fórmulas más generales que la fórmula de Cayley.

En este problema se nos da un grafo con $n$ vértices y $m$ aristas. El grafo tiene actualmente $k$ componentes. Queremos calcular el número de formas de agregar $k-1$ aristas de modo que el grafo se vuelva conexo (obviamente $k-1$ es el número mínimo necesario para hacer el grafo conexo).

Derivemos una fórmula para resolver este problema.

Usamos $s_1, \dots, s_k$ para los tamaños de las componentes conexas del grafo. No podemos agregar aristas dentro de una componente conexa. Por tanto resulta que este problema es muy similar a la búsqueda del número de árboles de expansión de un grafo completo con $k$ vértices. La única diferencia es que cada vértice tiene realmente el tamaño $s_i$: cada arista que conecta el vértice $i$ en realidad multiplica la respuesta por $s_i$.

Así, para calcular el número de formas posibles es importante contar cuántas veces se usa cada uno de los $k$ vértices en el árbol de conexión. Para obtener una fórmula del problema es necesario sumar la respuesta sobre todos los grados posibles.

Sean $d_1, \dots, d_k$ los grados de los vértices en el árbol después de conectar los vértices. La suma de los grados es el doble del número de aristas:

$$\sum_{i=1}^k d_i = 2k - 2$$

Si el vértice $i$ tiene grado $d_i$, entonces aparece $d_i - 1$ veces en el código de Prüfer. El código de Prüfer de un árbol con $k$ vértices tiene longitud $k-2$. Así, el número de formas de elegir un código con $k-2$ números donde el número $i$ aparece exactamente $d_i - 1$ veces es igual al coeficiente multinomial

$$\binom{k-2}{d_1-1, d_2-1, \dots, d_k-1} = \frac{(k-2)!}{(d_1-1)! (d_2-1)! \cdots (d_k-1)!}.$$

El hecho de que cada arista adyacente al vértice $i$ multiplica la respuesta por $s_i$ nos da la respuesta, asumiendo que los grados de los vértices son $d_1, \dots, d_k$:

$$s_1^{d_1} \cdot s_2^{d_2} \cdots s_k^{d_k} \cdot \binom{k-2}{d_1-1, d_2-1, \dots, d_k-1}$$

Para obtener la respuesta final necesitamos sumar esto para todas las formas posibles de elegir los grados:

$$\sum_{\substack{d_i \ge 1 \\ \sum_{i=1}^k d_i = 2k -2}} s_1^{d_1} \cdot s_2^{d_2} \cdots s_k^{d_k} \cdot \binom{k-2}{d_1-1, d_2-1, \dots, d_k-1}$$

Por ahora esto parece una respuesta realmente horrible, sin embargo podemos usar el teorema multinomial, que dice:

$$(x_1 + \dots + x_m)^p = \sum_{\substack{c_i \ge 0 \\ \sum_{i=1}^m c_i = p}} x_1^{c_1} \cdot x_2^{c_2} \cdots x_m^{c_m} \cdot \binom{p}{c_1, c_2, \dots c_m}$$

Esto ya se parece bastante. Para usarlo solo necesitamos sustituir con $e_i = d_i - 1$:

$$\sum_{\substack{e_i \ge 0 \\ \sum_{i=1}^k e_i = k - 2}} s_1^{e_1+1} \cdot s_2^{e_2+1} \cdots s_k^{e_k+1} \cdot \binom{k-2}{e_1, e_2, \dots, e_k}$$

Después de aplicar el teorema multinomial obtenemos la respuesta al problema:

$$s_1 \cdot s_2 \cdots s_k \cdot (s_1 + s_2 + \dots + s_k)^{k-2} = s_1 \cdot s_2 \cdots s_k \cdot n^{k-2}$$

Por accidente esta fórmula también vale para $k = 1$.

Problemas de práctica

• UVA #10843 - Anne’s game 
• Timus #1069 - Prufer Code 
• Codeforces - Clues 
• Topcoder - TheCitiesAndRoadsDivTwo