Problema del árbol de expansión mínima (II)

Este problema tiene muchas aplicaciones prácticas importantes. Por ejemplo, puede ser útil en la planeacion de redes de transporte que no se transmitirán mucho y en las que la inquietud principal es proporcionar algún tipo de conexión entre todos los pares de nodos de la manera más ecónomica. Los nodosserán las localidades que requieren acceso a otras localidades, las ligaduras serían las líneas de transporte (carreteras, vias de ferrocarril, vias aereas, etc.) y las "distancias" (valores de las ligaduras) serían los costos de proporcionar la comunicación. En este contexto, el problema del árbol de mínima expansión tiene como  objetivo determinar cuáles serián las líneas de comunicación que darían servicio a todas las localidades con un costo total mínimo. Otros ejemplos en los que surge una decisión parecida incluyen la pleanación de redes de comunicación y redes de distribución de gran escala. Ambos representa áreas de aplicación importantes.

El problema del árbol de mínima se puede resolver de una forma bastante directa, pues ocurre que se trata de uno de los pocos problemas de investigación de operaciones el que la codicia en cada etapa del procedimiento de solución iconduce al final a una solución óptima. Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto que esta elección pueda tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no conectado que esté más cerca de cualquiera de los dos que se acaban de conectar y después agregar la ligadura correspondiente la red. Este proceso se repetirá, según el resumen que se da a continuación, hasta que se hayan conectado todos los nodos. Se garantiza que la red resultante es un árbol de mínima expansión.