Árvore de extensão mínima: diferenças entre revisões

Dado um [[grafo unidirecional]] [[grafo conectado|conectado]], auma [[árvore de extensão (matemática)|árvore de extensão]] deste grafo é um [[subgrafo]] o qual é uma [[árvore (teoria dos grafos)|árvore]] que conecta todos os vértices. Um único grafo pode ter diferentes árvores de extensão. Nós podemos assinalar um ''peso'' a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma '''árvore de extensão mínima''' (também conhecida como '''árvore de extensão de peso mínimo''' ou '''árvore geradora mínima''') é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis. Generalizando mais, qualquer grafo não direcional (não necessariamente conectado) tem uma '''floresta de árvores mínimas''', que é uma união de árvores de extensão mínimas de cada uma de suas [[componente conexa|componentes conexas]]. Em um grafo não ponderado (sem peso nas arestas), qualquer árvore de extensão é mínima.