ÁRBOL DE EXPANSIÓN.

ÁRBOL DE EXPANSIÓN MÍNIMA.

 CARACTERISICAS : Es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.

ÁRBOL DE EXPANSIÓN MÍNIMA.

El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en al solución del problema.

ÁRBOL DE EXPANSIÓN MÍNIMA.

EL PROBLEMA DE HALLAR EL ÁRBOL  DE EXPANSIÓN MÍNIMA ( MST ) PUEDE SER RESUELTO CON VARIOS ALGORITMOS , LOS MAS CONOCIDOS COMO PRIM Y KRUSKAL AMBOS USAN TECNICAS VORACES .  

TÉCNICAS MAS CONOCIDAS:

PRIM: Es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado no dirigido. Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye todos los vértices, donde se minimiza el peso total de todos los bordes del árbol..

KRUSKAL.:  Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo.