El árbol de expansión mínima

Principal ] Arriba ] Contenido ] Acerca de esta página Web ] Bibliografía ]


 

 

Arboles de expansión minimales

Se aborda este concepto a partir del siguiente problema:

"Hay que construir una red de cómputo con un acoplamiento vago para un sistema de siete computadores. El grafo G de la figura es un modelo de la situación. Los computadores se representan mediante los vértices del grafo, las aristas representan Líneas de transmisión que se tienen en cuanta para enlazar ciertos pares de computadores. Asociamos a cada arista e de G un número real positivo p(e), el peso de e. En este ejemplo, el peso de una arista indica el costo previsto para la construcción de esa línea de transmisión particular. El objetivo es enlazar todos los computadores minimizando el costo total de la construcción."

A0.gif (3173 bytes)

Para hacer esto, se necesita un árbol de expansión T, tal que la suma de los pesos de las aristas en T sea mínima.

La construcción de dicho árbol de expansión óptimo se puede realizar por medio de los algoritmos de: Joseph Kruskal.y Robert Prim.


Principal
Arriba
Joseph Kruskal
Robert Prim