Código Prüfer

Neste artigo, veremos o chamado código Prüfer (ou sequência Prüfer), que é uma maneira de codificar uma árvore rotulada em uma sequência de números de uma maneira única.

Com a ajuda do código Prüfer, provaremos a fórmula de Cayley (que especifica o número de árvores geradoras em um grafo completo). Também mostramos a solução para o problema de contar o número de maneiras de adicionar arestas a um grafo para torná-lo conexo/conectado.

Nota: não consideraremos árvores que consistem em um único vértice - este é um caso especial em que várias declarações se "chocam".

Código Prüfer

O código Prüfer é uma maneira de codificar uma árvore rotulada com $n$ vértices usando uma sequência de $n - 2$ inteiros no intervalo $[0; n-1]$. Essa codificação também atua como uma bijeção entre todas as árvores geradoras de um grafo completo e das sequências numéricas.

Embora o uso do código Prüfer para armazenar e operar em árvores seja impraticável devido à especificação da representação, os códigos Prüfer são usados ​​com frequência principalmente na solução de problemas combinatórios.

O inventor - Heinz Prüfer - propôs esse código em 1918 como uma prova da fórmula de Cayley.

Construindo o código Prüfer para uma determinada árvore

O código do Prüfer é construído da seguinte maneira. Repetiremos o seguinte procedimento $n - 2$ vezes: selecionamos a folha da árvore com o menor número, removemos da árvore e escrevemos o número do vértice que estava conectado a ela. Após $n - 2$ iterações restarão apenas $2$ vértices, e então o algoritmo termina.

Assim, o código de Prüfer para uma determinada árvore é uma sequência de $n - 2$ números, onde cada número é o número do vértice conectado, ou seja, esse número está no intervalo $[0, n-1]$.

O algoritmo para calcular o código Prüfer pode ser implementado facilmente com a complexidade de tempo $O(n \log n)$, simplesmente usando uma estrutura de dados para extrair o mínimo (por exemplo: set ou priority_queue no C++), que contém uma lista de todos as folhas atuais.

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;
}

No entanto, a construção também pode ser implementada em tempo linear. Essa abordagem é descrita na próxima seção.

Construindo o código Prüfer para uma determinada árvore em tempo linear

A essência do algoritmo é usar um ponteiro em movimento que sempre apontará para o vértice atual da folha que queremos remover.

À primeira vista, isso parece impossível, porque durante o processo de construção do código de Prüfer, o número de folhas pode aumentar e diminuir. No entanto, após uma análise mais detalhada, isso não é verdade. O número de folhas não aumenta. Ou o número diminui em um (removemos um vértice folha e não obtemos um novo) ou permanece o mesmo (removemos um vértice folha e obtemos outro). No primeiro caso, não há outra maneira senão procurar pelo próximo menor vértice folha. se podemos continuar usando o vértice que se tornou um novo vértice folha ou se precisamos procurar o próximo menor vértice folha. E muitas vezes podemos continuar com o novo vértice folha.

Para fazer isso, usaremos uma variável $\text{ptr}$, que indicará que no conjunto de vértices entre $0$ e $\text{ptr}$ há no máximo um vértice folha, ou seja, o atual. Todos os outros vértices nesse intervalo já foram removidos da árvore ou ainda têm mais de um vértice adjacente. Ao mesmo tempo, dizemos que ainda não removemos nenhum vértice folha maior que $\text{ptr}$ ainda.

Essa variável já é muito útil no primeiro caso. Após remover o nó folha atual, sabemos que não pode haver um nó folha entre $0$ e $\text{ptr}$, portanto, podemos iniciar a pesquisa do próximo diretamente em $\text{ptr} + 1$, e não precisamos iniciar a pesquisa novamente no vértice $0$. E no segundo caso, podemos distinguir ainda mais dois casos: ou o vértice folha recém adquirido é menor que $\text{ptr}$, então esse deve ser o próximo vértice folha, pois sabemos que não existem outros vértices menores que $\text{ptr}$; ou o vértice folha recém adquirido é maior. Mas então, também sabemos que ele deve ser maior que $\text{ptr}$, e podemos iniciar a pesquisa novamente em $\text{ptr} + 1$.

Embora possamos ter que executar várias pesquisas lineares para o próximo vértice folha, o ponteiro $\text{ptr}$ apenas aumenta e, portanto, a complexidade do tempo no total é de $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;
}

No código, encontramos primeiro para cada parent[i] seu ancestral, ou seja, o ancestral que esse vértice terá depois que o removermos da árvore. Podemos encontrar esse ancestral enraizando a árvore no vértice $n-1$. Isso é possível porque o vértice $n-1$ nunca será removido da árvore. Também calculamos o grau para cada vértice. ptr é o ponteiro que indica o tamanho mínimo dos vértices folhas restantes (exceto o do atual). Atribuiremos o vértice folha atual com next, se este também for um vértice folha e for menor que ptr, ou iniciaremos uma pesquisa linear pelo menor vértice folha aumentando o ponteiro.

Pode-se ver que esse código possui a complexidade $O(n)$.

Propriedades do código Prüfer

Restaurando a árvore usando o código Prüfer

Para restaurar a árvore, basta focar apenas na propriedade discutida na última seção. Já sabemos o grau de todos os vértices na árvore desejada. Portanto, podemos encontrar todos os vértices folhas, e também a primeira folha que foi removida na primeira etapa (ela deve ser a menor). Esse vértice folha foi conectado ao vértice correspondente ao número na primeira célula do código Prüfer.

Assim, encontramos a primeira aresta removida quando o código do Prüfer foi gerado. Podemos adicionar essa aresta à resposta e reduzir os graus nas duas extremidades da aresta.

Repetiremos esta operação até usarmos todos os números do código de Prüfer: procuramos o vértice mínimo com grau igual a $1$, conectamos ele ao próximo vértice do código de Prüfer e reduzimos o grau.

No final, só temos dois vértices com grau igual a $1$. Estes são os vértices que não foram removidos pelo processo do código Prüfer. Nós os conectamos para obter a última borda da árvore. Um deles sempre será o vértice $n-1$.

Esse algoritmo pode ser implementado em $O(n \log n)$: usamos uma estrutura de dados que suporta a extração do mínimo (por exemplo: set<> ou priority_queue<> no C++) para armazenar todos os vértices folhas.

A implementação a seguir retorna a lista de arestas correspondentes à árvore.

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;
}

Restaurando a árvore usando o código Prüfer em tempo linear

Para obter a árvore em tempo linear, podemos aplicar a mesma técnica usada para obter o código de Prüfer em tempo linear.

Não precisamos de uma estrutura de dados para extrair o mínimo. Em vez disso, podemos notar que, depois de processar a aresta atual, apenas um vértice se torna uma folha. Portanto, podemos continuar com esse vértice ou encontrar um menor com uma pesquisa linear movendo um ponteiro.

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;
}

Bijeção entre árvores e códigos Prüfer

Para cada árvore existe um código Prüfer correspondente a ela. E para cada código do Prüfer, podemos restaurar a árvore original.

Segue-se que também todo código Prüfer (ou seja, uma sequência de $n-2$ números no intervalo $[0; n - 1]$) corresponde a uma árvore.

ortanto, todas as árvores e todos os códigos de Prüfer formam uma bijeção (uma correspondência individual ou de um para o outro.

Fórmula de Cayley

A fórmula de Cayley afirma que o número de árvores geradoras em um grafo "rotulado" completo (com $n$ vértices) é igual a: $$n^{n-2}$$ Existem várias provas para essa fórmula. Usando o conceito de código Prüfer podemos encontrar essa afirmação.

De fato, qualquer código Prüfer com $n-2$ números do intervalo $[0; n-1]$ corresponde a alguma árvore com $n$ vértices. Portanto, teremos $n^{n-2}$ diferentes códigos Prüfer. Como cada uma dessas árvores é uma árvore geradora de um grafo completo com $n$ vértices, o número dessas árvores geradoras também é $n^{n-2}$.

Número de maneiras de tornar um grafo conexo

O conceito dos códigos Prüfer é ainda mais poderoso, pois eles permitem criar muito mais fórmulas gerais do que a fórmula de Cayley.

este problema, temos um grafo com $n$ vértices e $m$ arestas. O grafo atual contém $k$ componentes. Queremos calcular o número de maneiras de adicionar $k-1$ arestas para que o grafo fique conectado (obviamente $k-1$ é o número mínimo necessário para conectar o grafo/tornar o grafo conexo).

Vamos derivar uma fórmula para resolver este problema.

Usamos $s_1, \dots, s_k$ para os tamanhos dos componentes conectados no grafo. Não podemos adicionar arestas dentro de um componente conectado. Portanto, esse problema é muito semelhante à pesquisa pelo número de árvores geradoras de um grafo completo com $k$ vértices. A única diferença é que cada vértice tem realmente o tamanho $s_i$: cada aresta conectando o vértice $i$, na verdade multiplica a resposta por $s_i$.

Portanto, para calcular o número de maneiras possíveis, é importante contar com que frequência cada um dos $k$ vértices é usado na árvore de conexão. Para obter uma fórmula para o problema, é necessário somar a resposta em todos os graus possíveis.

Seja $d_1, \dots, d_k$ os graus dos vértices na árvore após conectar os vértices. A soma dos graus é o dobro do número de arestas: $$\sum_{i=1}^k d_i = 2k - 2$$ Se o vértice $i$ tem grau $d_i$, então aparece $d_i - 1$ vezes no código Prüfer. O código do Prüfer para uma árvore com $k$ vértices tem tamanho $k-2$. Portanto, o número de maneiras de escolher um código com $k-2$ números em que o número $i$ apareça exatamente $d_i - 1$ vezes é igual ao 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)!}.$$ O fato de que cada aresta adjacente ao vértice $i$ multiplica a resposta por $s_i$ e assumindo que os graus dos vértices são $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 obter a resposta final, precisamos somar isso para todas as formas possíveis de escolher os graus: $$\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}$$

Isso parece uma resposta realmente horrível, no entanto, podemos usar o teorema multinomial , que diz: $$(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}$$ Para usá-lo, basta substituir $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}$$ Após aplicar o teorema multinomial, obtemos a resposta para o 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 "acidente", esta fórmula também vale para $k = 1$.

Problemas