Arboles Generadores Mínimales

 Un Arbol Generador Minimal es el que resulta de la construcción en primer lugar de un Arbol generador, pero con la característica de ser el de menos peso del grafo al cual genera. Por ejemplo sea un grafo ponderado ( con peso) con cinco vértices. La idea es construir un subgrafo que una a todos los puntos pero con el mínimo de peso (el peso se refiere al valor que se le da a cada uno de los lados de un grafo). Este subgrafo debe ser un árbol generador, ya que debe unir todos los vértices, debe ser conexo y debe haber un único camino entre cada par de vértices, por lo tanto, lo que se necesita es un árbol generador con el mínimo de peso, es a esto lo que se llama árbol generador minimal. Sea G un grafo con peso. Un árbol generador mínimal de G es un árbol generador de G con peso mínimo. Ejemplo:

Sea el Grafo G :

 










Los Arboles T1 y T2 son arboles generadores de G, sin embargo el peso de ambos es distinto (T1=32 y T2=41). Por lo tanto el Arbol Generador Minimal de G es T1. Arboles Generadores Minimales se pueden generar con algoritmos como el Algoritmo de Prim, el cual construye un árbol en forma iterativa, agregando lados hasta obtener un árbol generador minimal. En cada iteración se coloca un lado de peso mínimo que no forme un circuito con el árbol que se ha construido con iteraciones anteriores.

Este algoritmo es un ejemplo de algoritmo voraz, el cual optimiza la selección hecha en cada iteración sin considerar las elecciones que corresponden a iteraciones anteriores.

Otro algoritmo que origina un árbol generador minimal en un grafo G de n vértices, conexo y con peso es el Algoritmo de Kruskal. Este parte con un grafo T que contiene inicialmente todos los vértices y ningún lado. en cada iteración se agrega un lado a T de peso mínimo, tal que no complete un circuito en T. Cuando T tenga n-1 lados, se termina.