Grafos: Árvores Geradoras Mínimas (MST)

Introdução Teórica

Dada uma rede conectada com pesos, uma Árvore Geradora Mínima (Minimum Spanning Tree - MST) é um subconjunto de arestas que conecta todos os vértices, não possui ciclos e tem a soma total dos pesos mínima.

Algoritmos

Ambos são gulosos, mas operam de formas distintas: 1. Algoritmo de Kruskal: * Ordena todas as arestas por peso crescente. * Itera e adiciona a aresta se ela conecta dois componentes diferentes (usa Union-Find / DSU). * Ótimo para grafos esparsos. 2. Algoritmo de Prim: * Começa de um nó arbitrário. * Mantém os nós “na árvore” e expande sempre com a aresta de menor peso conectando um nó de dentro a um de fora (usa Priority Queue). * Ótimo para grafos densos.

Problema Clássico

Problema: Estradas Escuras Link: Beecrowd 1152

Descrição: O governo quer economizar energia desligando iluminação de estradas, mas garantindo que toda cidade ainda esteja conectada a todas as outras. Qual a economia máxima?

Solução: A economia máxima é (Soma Total de todas as arestas) - (Soma da MST). Basta rodar o Kruskal e subtrair.

Variações e Exercícios

  1. [Rede Ótica]
    • Foco: MST simples para garantir conectividade.
    • Link: Beecrowd 1774 (Roteadores).
  2. [Espaço de Projeto]
    • Foco: Interpretar o problema como MST.
    • Link: [Beecrowd 2562] (Não, esse é Analógico/Componentes). Procure Beecrowd 1550 (Na verdade, Inversão é BFS).
    • Sugestão: Beecrowd 2404 (Reduzindo Detalhes em um Mapa - MST Clássico).
  3. [Mini-Max Path (UVa 10048)]
    • Conceito: O caminho entre A e B que minimiza a aresta de maior peso passa unicamente pelas arestas da MST.
Back to top