Árvores Geradoras

Uma árvore geradora de um grafo não dirigido G=(V,E) é um subgrafo T com os mesmos vértices, conexo e acíclico. Com n=|V|, T tem exatamente n−1 arestas e um único caminho entre cada par.

A árvore geradora mínima (AGM) é uma geradora de menor soma w(T). Prim e Kruskal deste tópico escolhem quais n−1 arestas entram nessa soma; o tópico de algoritmos em grafos reusa o mesmo T.

As páginas se agrupam em três blocos. O primeiro reconhece geradora e AGM sem executar algoritmo: G conexo garante existência; n−1 arestas amontoadas num subconjunto ainda deixam ciclo e vértice isolado; pesos todos distintos tornam a AGM única.

O segundo cresce um conjunto S a partir de um vértice qualquer. A cada passo entra a aresta mais leve que cruza o corte (S, V∖S).

O terceiro ordena todas as arestas por peso não decrescente e aceita uma só se os extremos ainda estão em componentes distintos. Ao completar n−1 arestas a floresta vira árvore.

Filtrar um subgrafo por cobertura de V, n−1 e caminho único, depois comparar w(T) entre geradoras já dadas, está em Características das Árvores Geradoras. Produzir a AGM passo a passo está em Algoritmo de Prim e em Algoritmo de Kruskal.

A aresta mínima da fronteira de S, com vértice inicial livre, está em Algoritmo de Prim. A lista global ordenada, pulando extremos no mesmo componente, está em Algoritmo de Kruskal.

A propriedade do corte — alguma AGM contém a aresta mais leve da partição — está em Algoritmo de Prim. O teste find(u)=find(v) que recusa ciclo, e a floresta que resta se a lista acaba antes de n−1, estão em Algoritmo de Kruskal.