Considere uma árvore que contém todo e qualquer nó em um
grafo, mais formalmente, uma spanning tree de um grafo G = (N,
E) e um grafo G' = (N, E') tal que E' é um subconjunto de E, G' é
conectado, G' não contém nenhum ciclo e G' contém todos os
nós originais em G.
Se cada enlace tiver um custo associado e o custo de uma árvore
for a soma dos custos dos enlaces, é correto afirmar que uma
árvore cujo custo seja o mínimo entre todas as spanning trees é
denominada: