Algoritmo Krukal
Enviado por pablogog • 19 de Diciembre de 2012 • 389 Palabras (2 Páginas) • 365 Visitas
El problema del árbol de mínima expansión
Una aplicación típica de este problema es el diseño de las redes telefónicas. Una
empresa con diferentes oficinas,trata de trazar líneas de teléfono para conectarlas
unas con otras.La compañía telefónica le ofrece esta interconexión, pero ofrece
tarifas de diferentes costes por conectar cada par de oficinas. ¿Cómo conectar
entonces las oficinas al mínimo coste total?
La formulación del árbol de mínima expansión MST (Minimal Spanning Tree)
también ha sido aplicada para hallar soluciones en diversas áreas como el diseño
de las redes de transporte, diseño de redes de comunicaciones, TV por cable,
internet , etc. En todos estos problemas tenemos una serie de nodos con posibles
uniones entre ellos a distintos costes y el objetivo es unir todos los nodos a coste
mínimo
Un árbol de expansión de un grafo es un subgrafo que contiene todos sus vértices
o nodos. Un grafo puede tener múltiples árboles por esto existen algoritmos para
encontrar el árbol de coste mínimo.Este problema fue resuelto por Dijkstra (1959),
Kruskal (1956) y Prim (1957). A lo largo de la historia se ha hecho un gran
esfuerzo para encontrar un algoritmo rápido para este problema.
El algoritmo de Kruskal
Kruskal es un algoritmo voraz en la teoría de grafos,que encuentro el mínimo árbol
de expansión entre un árbol con pesos. Es decir, el algoritmo busca subconjunto
de aristas, que formando un árbol, incluye todos los vértices donde el valor total de
las aristas del árbol es el mínimo. Este algoritmo fue publicado por primera vez
en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue
escrito porJoseph Kruskal.
El algoritmo Funciona de la siguiente manera:
se crea un bosque B (un conjunto de árboles), donde cada vértice
...