árvore de extensão

Uma árvore de extensão ou árvore de dispersão (em inglês: spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices. Uma árvore de extensão mínima ou árvore de extensão de custo mínimo (em inglês: minimum spanning tree) é o subconjunto de arestas de menor peso total em um grafo valorado que forma uma árvore contendo todos os nós. Uma árvore de extensão/dispersão apresenta as seguintes propriedades: * Define um subconjunto de arestas que mantém o grafo conectado em um único componente; * Em um grafo não-valorado qualquer árvore de dispersão é mínima; * Podem ser calculadas em tempo polinomial. Os algoritmos usuais para a determinação de árvores de extensão/dispersão são o algoritmo de Prim (1957) e o algoritmo de Kruskal (1956).