Arbol De Expansion

Árbol de Expansión Mínima

Un árbol de expansión es un modelo que conecta todos los nodos de una red, los nodos están conectados por arcos o líneas (que son n-1 arcos). Este debe formar un recorrido pasando por todos los nodos sin formar ciclos.

Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un ciclo. El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

Un problema de árbol de expansión mínima se refiera a utilizar las ramas o arcos de la red para llegar a todos los nodos de la red de manera tal que se minimiza la longitud total del recorrido.

La aplicación de estos problemas de optimización se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc.; donde los nodos representan los puntos de consumo eléctrico, telefónico, aeropuertos y computadoras. Y los arcos podrían ser la alta tensión, cable de fibra óptica, rutas aéreas, etc. Si n= numero de nodos, entonces la solución optima debe incluir n-1 arcos.

Ejemplo

Se va a instalar una red de comunicación entre 12 ciudades. Los costos de los posibles enlaces directos entre pares permisibles es el que se muestra en la figura. Cada unidad de costo representa $10,000 dólares.

Paso1

Encontrar el menor costo: en este caso sería el 1, si hubiese empate entre un valor mínimo, se elige tomando el orden letárgico entre los nodos, por lo tanto empezamos con el nodo 1.

Nota:

Una vez hecha una ruta, se descarta del recorrido al nodo ya seleccionado para evitar volverlo a seleccionar y formar ciclos.

Paso 3

Ahora debemos elegir el menor costo entre todos los destinos que puedes tomar a partir del nodo 1 o el nodo 5. Como hay un empate entre el costo de ir del nodo 1 al nodo 2 y el costo de ir del nodo 5 al nodo 6, se elige tomando en cuenta la jerarquía del menor a mayor, eligiendo el nodo 2 como nuestro siguiente destino.

En cuestión, para resolver este problema solo se repite el proceso hasta haber recorrido cada uno de los nodos sin formar ciclos. En este caso el costo mínimo sería el de ir entre el nodo 3 al nodo 6, con un costo de 3

Ahora el costo mínimo seria 4, el de ir del nodo 6 al nodo 5 pero no debemos formar ciclos, asique el siguiente costo mínimo seria el 5, que corresponde a ir del nodo 6 al 7

Repetimos el proceso el costo mínimo es 2, corresponde a ir del nodo 7 al nodo 11.

Escogimos

...