ARBOLES DE EXPANSIÓN MÍNIMA

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).