Published

22/04/2026

Modified

22/04/2026

Programação Dinâmica em Árvores (Vertex Cover)

Metáfora e Motivação

A Programação Dinâmica brilha ao fatiar problemas em sub-problemas progressivamente menores. Em matrizes, a progressão era ir pela direita ou pra baixo. Mas como fazer transições numa Árvore/Grafo? O sub-problema de uma árvore é simplesmente olhar para uma ramificação inferior cortando o tronco acima!

O Problema do Reino (Vertex Cover)

Um reino possui \(N\) cidades conectadas entre si por \(N-1\) estradas perfeitamente pavimentadas (Grafo Conexo sem ciclos = Uma Árvore). A rainha precisa erguer postos militares em algumas cidades. Acordo estrito: para toda estrada, pelo menos uma das duas cidades interligadas deve ter um posto! Os postos custam caro. Qual o menor número de postos que podemos erguer e cobrir todas as estradas?

Na matemática de grafos, isso é conhecido como a Cobertura Mínima de Vértices (Vertex Cover). Sendo a geografia local formatada em árvore, podemos achar a raiz matematicamente de forma linear.

O Estado da Construção Dinâmica

Vamos batizar um vértice escolhido como Colorido (Instalamos o posto) ou Branco.

Na árvore, ao olharmos os galhos de cima para baixo começando na base 1, o que um nó da camada atual precisa saber do próprio passado? Ele precisa saber “Meu pai no tronco de cima foi colorido?” Por que? Porque se o pai dele não instalou um posto militar lá em cima, essa mesma cidade que estamos lendo Têm que, de forma divina e obrigatória, instalar o posto, senão a estrada entre ela e o pai ficaria sem proteção em ambos os lados!

  • Estado da DP: PD(CidadeAtual, PaiColorido_Boolean)
    • Possibilidade A (Colorir): Gastamos +1 instalação. Ganhamos carta branca pra todos os filhos (Eles herdarão PaiColorido = True).
    • Possibilidade B (Não Colorir): Não gastamos grana (\(0\)). Mas sentenças duras passam aos nossos filhos (Herdarão PaiColorido = False), obrigando-os a se colorir sem piedade.
    • Se a aba PaiColorido_Boolean == False, o universo te obriga atuar a Possibilidade A. Senão, use a força da DP e explore e pegue o min(A, B).

Algoritmo Vertex Cover Recursivo em DP

Este código injeta os conceitos acima no formato Top-Down, construindo uma tabela que varia de acordo com as respostas vizinhas.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cassert>

using namespace std;

const int MAXV = 1000;
int tabelaDP[MAXV][2];
vector<int> arvore[MAXV];

// X: Fator Posicional da Árvore
// paiColorido: 1 (Verdadeiro), 0 (Falso)
// paiN: Nó que realizou a chamada para evitar voltar pra cima infinitamente na recursao.
int vertexCover(int X, int paiColorido, int paiN) {
    if(tabelaDP[X][paiColorido] != -1) {
        return tabelaDP[X][paiColorido];
    }
    
    int custoColorir = 1; // +1 posto na cidade X
    int custoNaoColorir = 0; // Economizamos 

    for(int filho : arvore[X]) {
        if(filho == paiN) continue; // Ignora ciclo subindo
        
        // Se X é colorido, o filho recebe (True) na chamada
        custoColorir += vertexCover(filho, 1, X);
        
        // Se X nao eh colorido, o filho recebe (False) na chamada obrigatoria futuramente 
        custoNaoColorir += vertexCover(filho, 0, X);
    }
    
    // Regulação da Decisão Exclusiva
    if(paiColorido == 0) {
        // Se meu pai era um desertor de bases, EU SOU OBRIGADO A ASSUMIR!
        return tabelaDP[X][paiColorido] = custoColorir;
    } 

    // Se o pai for colorido, eu tenho a margem de escolha livre.
    return tabelaDP[X][paiColorido] = min(custoColorir, custoNaoColorir);
}

void executando_testes() {
    // 5 cidades modelados (Indices 1 ao 5)
    // Ligacoes: 1-2, 1-3, 2-4, 2-5
    arvore[1] = {2, 3};
    arvore[2] = {1, 4, 5};
    arvore[3] = {1};
    arvore[4] = {2};
    arvore[5] = {2};

    memset(tabelaDP, -1, sizeof(tabelaDP));
    
    // Para resolver, entramos na Raiz (1) dizendo que seu "pai imaginário superior" ERA colorido (1).
    // Isso dá passe livre para a base raiz decidir sozinha e sem restrições.
    int menorTotal = vertexCover(1, 1, -1);
    
    // O ideal seria colocar o Posto na Capital 1, e na Metropole 2! (Atrapalhando todas as vizinhancas)
    // Assim gastaria 2 postos (Node 1, Node 2)
    assert(menorTotal == 2);
    
    cout << "[✅] Testes Dinâmicos do Vertex Cover Tree aprovados!\n";
}

int main() {
    executando_testes();
    return 0;
}

O poder da Programação Dinâmica em árvores é que essa matriz de memorização só armazena linearmente de 0 a \(N\). Complexidade \(\mathcal{O}(2N)\) ou puramente temporal \(\mathcal{O}(N)\) de processamento na máquina iterativa.

Exercício Prático

  • O caso explícito do Independent Set On Trees também navega nisso. É a versão onde o estado dita regras de não colisão vizinha (\(DP[X][0]\) vs \(DP[X][1]\)). Procure-o nas maratonas Beecrowd / UVa!
Back to top