CLASE 18. ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓNING. LUIS MORALES MG.

INVESTIGACIÓN OPERATIVA

ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓN Este árbol vincula los nodos de una red valiéndose de la longitud mínima total de las ramas de conexión.

Una aplicación común se presenta en la pavimentación de carreteras que unen poblaciones, o de forma directa, o que pasan por otras poblaciones

ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓN

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.

El problema surge cuando todos los nodos de una red deben conectarse entre ellos sin formar un círculo.

ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓN

Se le conoce como árbol generador mínimo, es una red conexa y ponderada que se refiere a utilizar los arcos de la red para llegar a todos los nodos de ésta, de manera tal que se minimiza la longitud total. Para la solución se emplean los algoritmos de PRIM y KRUSKAL.

ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓN La solución del árbol de mínima expansión proporciona el diseño del sistema de carreteras. Sea N = {1, 2,…,n} el conjunto de nodos de la red. Ck = Conjunto de nodos que han estado conectados de manera permanente en la iteración k = Conjunto de nodos que se construirán permanentemente después de la iteración k.

ALGORITMO DEL ÁRBOL DE MÍNIMA EXPANSIÓN Los siguientes pasos describen al algoritmo del árbol de mínima expansión:

ALGORITMO DE KRUSKAL