Dado un grafo conexo y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso.
Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:
Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:
De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.
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 nodo de una red deben conectarse entre ellos sin formar un ciclo.
Para la solución empleamos los algoritmos de kruskal y de prim.
0 comentarios :
Publicar un comentario