PROBLEMA DEL ARBOL DE EXPANSION MINIMA

PROBLEMA DEL ARBOL DE EXPANSION MINIMA

El problema de árbol de expansión mínima tiene algunas similitudes con la versión principal de la ruta más corta que se presento en la sección anterior. En ambos casos se considera una red no dirigida y conexa, en la que la información dada incluye alguna medida de longitud positiva- distancia, costo, tiempo, etc.- asociada con cada ligadura.

El problema de árbol de expansión mínima se puede resumir de la siguiente manera:

1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud de cada una si se insertan en la red. (las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)

2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.

3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.

Una red n nodos requiere solo (n-1) ligaduras para proporcionar una trayectoria en cada par de nodos. No deben usarse más ligaduras puesto que ello aumentaría, sin necesidad la longitud total de las ligaduras seleccionadas. Las (n-1) ligaduras deben elegirse de tal manera que la red resultante con solo las ligaduras seleccionadas forme un árbol de expansión, según la definición que se presento.

ALGUNAS APLICACIONES

A continuación se proporcionan una lista de algunos tipos importantes de aplicaciones de este problema.

1. Diseño de redes de telecomunicaciones (redes de fibra óptica, de computadoras, telefónicas, de televisión por cable, etc.)

2. Diseño de redes por transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etcétera).

3. Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje.

4. Diseño de una red de cableado de equipo eléctrico como sistemas de computo para minimizar la longitud total de cable.

5. Diseño de una red de tuberías para conectar varias localidades.

En esta era de la supercarretera de la información, las aplicaciones del primer tipo han cobrado una importancia especial, pues una red de telecomunicaciones solo es necesario insertar suficientes ligaduras para que proporcionen una trayectoria entre cada par de nodos, de modo que el diseño de tales redes es una aplicación clásica del problema del árbol de expansión mínima. Debido a que la actualidad de algunas redes de comunicación cuestan muchos millones de dólares, es muy importante optimizar su diseño al encontrar el árbol de expansión mínima.

UN ALGORITMO

El problema del árbol de expansión mínima se puede resolver de una forma bastante directa, puesto que se trata de uno de los pocos problemas de IO en el que ser codicioso en cada etapa del procedimiento de solución conduce al final a una solución optima. 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 puede tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no conectado que esta más cerca de cualquiera de las dos que acaban de conectar y después agregar la ligadura correspondiente a la red. Este proceso se repite, según el resumen que se presenta a continuación, hasta conectar todos los nodos.

Algoritmo del problema del árbol de expansión mínima.

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta, es decir,

...