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

Dado um [[grafo uniderecionalunidirecional]] [[grafo conectado|conectado]], [[árvore de extensão (matemática)|árvore de extensão]] deste grafo é um [[subgrafo]] o qual é uma [[grafo de árvore|árvore]] que conecta todos os vértices. Um único grafo pode ter diferentes árvore de extensão. Nos 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''' ou '''árvore de extensão de peso mínimo'' é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão. Generalizando mais, qualquer grafo não direcional tem uma '''floresta de árvores mínimas'''.

[[Categoria:Teoria dos Grafosgrafos]]