ALGORITMO DE KRUSKAL
El algoritmo
de Kruskal es un algoritmo de la teoría de grafos que se usa para
encontrar un árbol recubridor en un grafo conexo
y poderado.
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.
Historia
Joseph B. Kruskal , en 1956 descubrió este algoritmo para la
resolución del problema Árbol de coste total mínimo (mínimum spinning tree -
MST) también llamado árbol recubridor euclídeo mínimo.
Este es un problema típico de optimización combinatoria, que
fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la
necesidad de electrificación rural en el sur de Moravia en
Checoslovaquia.
Aspectos interesantes
La aplicación típica de este problema
es el diseño de
redes telefónicas.
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 diferentes o
costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas
al mínimo coste total.
La formulación del algoritmo también ha sido aplicada para hallar
soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de
telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de
datos climatológicos, visión artificial - análisis de imágenes - extracción de
rasgos de parentesco, plegamiento de proteínas, reconocimiento de células
cancerosas, y otros).
Ejemplos
Grafo
Pseudocódigo
Kruskal (G)
E(1)=0, E(2)= todos los Arcos del grafo G
Mientras E(1) contenga menos de n-1 arcos y E(2)=0 do
De los arcos de E(2) seleccionar el de menor coste -->e(ij)
E(2)= E(2) - {e(ij)}
Si V(i), V(j) no están en el mismo árbol entonces
juntar los árboles de V(i) y de V(j) en uno sólo
Finaliza Si
Finaliza Mientras
Fin del algoritmo
Bibliografía
Video
No hay comentarios.:
Publicar un comentario