Árvores Geradoras Mínimas

Para um grafo conexo, não direcionado e com pesos, uma árvore geradora mínima (MST) conecta todos os vértices sem ciclos e minimiza o peso total das arestas. Ela minimiza o peso total da árvore, não a distância dos caminhos entre todos os pares.

Propriedade do corte

Para um corte que divide os vértices em dois conjuntos, uma aresta de peso mínimo que cruza o corte é segura para alguma MST. Essa propriedade fundamenta os dois algoritmos principais.

Algoritmo de Kruskal

1. Ordene todas as arestas por peso não decrescente.
2. Percorra-as nessa ordem.
3. Adicione uma aresta exatamente quando suas extremidades estiverem em conjuntos disjuntos diferentes.

Union–find torna eficiente o teste de ciclos. A ordenação domina o custo, com O(E log E), equivalente a O(E log V) nos limites usuais de grafos simples. Uma entrada desconectada produz uma floresta geradora mínima.

Algoritmo de Prim

Comece por qualquer vértice e adicione repetidamente a aresta mais leve que parte da árvore atual para um vértice externo. Com listas de adjacências e um heap binário, o tempo é O(E log V).

Unicidade

Pesos de arestas distintos implicam uma MST única, mas pesos iguais não implicam necessariamente múltiplas MSTs. Critérios de desempate podem selecionar árvores válidas diferentes com o mesmo peso total mínimo.

Exercícios

1. Execute Kruskal passo a passo usando a estrutura de conjuntos disjuntos.
2. Dê um grafo cuja árvore de caminhos mínimos não seja uma MST.
3. Prove que adicionar uma aresta a uma árvore cria exatamente um ciclo.