Árvores abrangentes de custo mínimo

Corte e escolha segura

Corte $(S,V\setminus S)$; aresta atravessa com extremos em lados opostos. $A$ respeita corte sem o atravessar.

Se $A$ está em alguma MST e $e$ é a mais leve a atravessar corte respeitado, $A\cup\{e\}$ continua em alguma MST. Troca $e$ por outra $f$ do ciclo criado, com $w(e)\le w(f)$. Acíclico só não chega: triângulo $1,2,10$ com $10$ primeiro não completa MST.

Kruskal e Prim

Algoritmo	Escolha	Estrutura	Custo
Kruskal	Aresta mais leve entre componentes distintas	Union-find	$O(m\log m+n)$; simples conexo $O(m\log n)$
Prim	Vértice exterior com menor key desde $S$	Heap ou matriz	$O((n+m)\log n)$; denso $O(n^2)$ com matriz

• Para após $n-1$ aceitações.
• key[v] é peso de aresta desde $S$, não distância à raiz como em Dijkstra.
• Variante com heap de arestas e descarte de internas: $O(m\log m+n)$.

Floresta e empates

• Desconexo: Kruskal dá floresta mínima; Prim reinicia por componente. Componente isolada custa zero.
• Heap vazia ou chave infinita não é aresta fictícia.
• Pesos iguais permitem várias MST; desempate torna determinístico sem mudar definição.
• Pesos todos distintos implicam MST única.

MST não é árvore de caminhos mínimos

Triângulo $ab=2$, $bc=2$, $ac=3$: MST usa $ab,bc$ com total 4, mas caminho $a\to c$ na árvore custa 4 contra 3 direto. MST minimiza soma total; árvore de Dijkstra minimiza cada distância à origem.

Exemplo e provas.