Introdução

As sequências de Prufer são uma representação matemática elegante para árvores não enraizadas, amplamente utilizada em problemas de contagem e teoria dos grafos. Esta nota técnica explora essa representação e suas aplicações práticas.

Conceito Básico de Sequências de Prufer

Uma sequência de Prufer é uma codificação que transforma uma árvore não enraizada com n vértices rotulados em uma sequência de n-2 inteiros no intervalo [1, n]. Essa transformação estabelece uma bijection entre todas as árvores geradoras do grafo completo de n vértices e as possíveis sequências de Prufer.

Essa técnica é particularmente útil para resolver problemas de enumeração e contagem relacionados a estruturas de árvore.

Conversão de Árvore para Sequência de Prufer

O processo de construção da sequência segue os passos:

1. Identificar o vértice folha com menor rótulo.
2. Remover esse vértice e registrar o rótulo do vértice adjacente ao qual estava conectado.
3. Repetir o processo até que apenas dois vértices permaneçam.

A implementação direta tem complexidade O(n log n). Uma abordagem mais eficiente utiliza um ponteiro para manter o rótulo da folha atual e otimiza a busca por novas folhas quando necessário.

Conversão de Sequência de Prufer para Árvore

A partir de uma sequência de Prufer, podemos determinar o grau de cada vértice na árvore original. Um vértice com grau d aparece exatamente d-1 vezes na sequência, pois cada remoção de um filho corresponde a uma inserção na sequência.

O algoritmo de reconstrução funciona assim:

1. Iniciar com uma sequência de vértices [1, n] e a sequência de Prufer.
2. Selecionar o vértice de menor rótulo que não está na sequência (grau 1) e conectá-lo ao primeiro elemento da sequência de Prufer.
3. Remover ambos os vértices de suas respectivas sequências.
4. Após n-2 iterações, conectar os dois vértices restantes.

Essa abordagem pode ser implementada com complexidade O(n).

Implementação Algorítmica

A seguir apresentamos uma implementação completa em C++:

// Implementação de sequências de Prufer
const int MAX_N = 5000100;
int num_vertices, opcao, grau[MAX_N], ancestral[MAX_N], sequencia_prufer[MAX_N];
long long resultado = 0;

void arvore_para_prufer() {
    memset(grau, 0, sizeof(grau));
    for (int i = 1; i < num_vertices; i++) {
        ancestral[i] = ler_dado();
        grau[ancestral[i]]++;
    }
    
    for (int i = 1, pos = 1; i <= num_vertices - 2; i++) {
        while (grau[pos]) pos++;
        sequencia_prufer[i] = ancestral[pos];
        
        for (; i <= num_vertices - 2; ) {
            grau[sequencia_prufer[i]]--;
            if (grau[sequencia_prufer[i]]) break;
            if (sequencia_prufer[i] >= pos) break;
            sequencia_prufer[i+1] = ancestral[sequencia_prufer[i]];
            i++;
        }
        pos++;
    }
    
    for (int i = 1; i <= num_vertices - 2; i++)
        resultado ^= (1LL * i * sequencia_prufer[i]);
    
    printf("%lld\n", resultado);
}

void prufer_para_arvore() {
    memset(grau, 0, sizeof(grau));
    for (int i = 1; i <= num_vertices - 2; i++) {
        sequencia_prufer[i] = ler_dado();
        grau[sequencia_prufer[i]]++;
    }
    sequencia_prufer[num_vertices - 1] = num_vertices;
    
    for (int i = 1, pos = 1; i < num_vertices; i++) {
        while (grau[pos]) pos++;
        ancestral[pos] = sequencia_prufer[i];
        
        for (; i < num_vertices - 1; ) {
            grau[sequencia_prufer[i]]--;
            if (grau[sequencia_prufer[i]]) break;
            if (sequencia_prufer[i] >= pos) break;
            ancestral[sequencia_prufer[i]] = sequencia_prufer[i+1];
            i++;
        }
        pos++;
    }
    
    for (int i = 1; i < num_vertices; i++)
        resultado ^= (1LL * i * ancestral[i]);
    
    printf("%lld\n", resultado);
}

int principal() {
    num_vertices = ler_dado();
    opcao = ler_dado();
    if (opcao == 1) arvore_para_prufer();
    else prufer_para_arvore();
    
    return 0;
}

Fórmula de Cayley

Devido ao fato de existirem n^(n-2) sequências de Prufer diferentes para n vértices, estabelece-se uma relação bijetiva que leva à seguinte conclusão:

Existem exatamente n^(n-2) árvores não enraizadas com n vértices rotulados.

Generalização:

Se cada vértice i tem grau d_i, o número de árvores correspondentes é (n-2)!/(∏(d_i-1)!).

Generalização da Fórmula de Cayley

Considere f(n, m) como o número de árvores com n vértices formando m componentes conexas, onde os vértices de 1 a m pertencem a componentes distintas. Temos:

f(n, m) = m·n^(n-m-1)

A fórmula de Cayley é um caso particular quando m = 1.

Extensões com Pesos

Para n vértices com pesos, onde o peso de uma aresta é o produto dos pesos dos vértices que ela conecta, e o peso de uma árvore é o produto dos pesos de suas arestas, a soma dos pesos de todas as árvores não enraizadas com n vértices é:

(∏ val_i)·(∑ val_i)^(n-2)

Exercícios Resolvidos

Contagem de Árvores com Graus Prescritos

Dado um número n de vértices, onde cada vértice i tem grau prescrito d_i, determine quantas árvores distintas satisfazem essa condição.

Solução:

Aplicamos diretamente a fórmula (n-2)!/(∏(d_i-1)!). Para evitar precisão numérica, podemos usar uma técnica de enumeração combinatória progressiva.

Seja S a soma dos (d_i-1) já processados. Para cada novo (d_i-1), o número de escolhas é C(n-2-S, d_i-1), onde C é o coeficiente binomial.

Casos especiais a considerar:

• n = 1: verificar se d_1 = 0
• A soma total dos graus deve ser 2n-2
• Não pode existir vértice com grau 0

const int MAX_N = 160;
int n, grau[MAX_N];
long long C[MAX_N][MAX_N];

void pre_combinatorios() {
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
}

int principal() {
    n = ler_dado();
    if (n == 1) {
        grau[1] = ler_dado();
        if (grau[1] == 0) printf("1");
        else printf("0");
        return 0;
    }

    pre_combinatorios();
    int soma = 0;
    for (int i = 1; i <= n; i++) {
        grau[i] = ler_dado();
        if (!grau[i]) { printf("0"); return 0; }
        grau[i]--;
        soma += grau[i];
    }
    if (soma != (n-2)) { printf("0"); return 0; }
    
    soma = 0;
    long long resposta = 1;
    for (int i = 1; i <= n; i++) {
        resposta = resposta * C[n-2-soma][grau[i]];
        soma += grau[i];
    }

    printf("%lld\n", resposta);
    return 0;
}

Problema da Enumeração com Restrições Parciais

Dado n vértices rotulados, e restrições parciais nos graus de alguns vértices, determine quantas árvores satisfazem essas restrições.

Solução:

Seja k o número de vértices com grau não restrito. Seja S = ∑(d_i-1) para os vértices restritos.

O número de árvores é:

C(n-2, S)·(S!)/(∏(d_i-1)! para vértices restritos)·(n-k)^(n-2-S)

Resultado Importante: Problema CF156D

Dado um grafo não direcionado com n vértices e m arestas, dividido em k componentes conexas, determnie quantas maneiras existem para adicionar k-1 arestas tornando o grafo conexo.

Tratando cada componente como um super vértice, podemos usar a contagem de Prufer:

∑(k-2)!/(∏(d_i-1)!), onde d_i ≥ 1 e ∑d_i = 2k-2

Cada componente deve contribuir com um vértice de conexão. Se |V_i| é o tamanho do i-ésimo componente, a solução completa é:

∑(k-2)!/(∏(d_i-1)!)·∏|V_i|^d_i

Aplicando o teorema binomial multivariado com b_i = d_i-1, obtemos:

n^(k-2)·∏|V_i|

int principal() {
    int n = ler_dado(), m = ler_dado(), modulo = ler_dado();
    if (modulo == 1) { puts("0"); return 0; }
    
    for (int i = 1; i <= n; i++) pai[i] = i;
    for (int i = 1, u, v; i <= m; i++) {
        u = ler_dado(), v = ler_dado();
        u = encontrar(u), v = encontrar(v);
        pai[u] = v;
    }
    
    for (int i = 1; i <= n; i++)
        tam[encontrar(i)]++;
    
    long long resposta = 1;
    for (int i = 1; i <= n; i++)
        if (i == encontrar(i)) {
            k++;
            resposta = (resposta * tam[i]) % modulo;
        }
    
    if (k == 1) { puts("1"); return 0; }
    
    resposta = resposta * potencia(n, k-2, modulo) % modulo;
    printf("%lld\n", resposta);
    return 0;
}

Material de Referência

• Notas de estudo sobre sequências de Prufer e Fórmula Generalizada de Cayley
• Solução de problemas modelo por xht37