Algoritmo de Kruskal

HISTORIA

Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010)1 fue un matemático y estadístico estadounidense.

Biografía

Investigador del Math Center (Bell-Labs), en 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo, el cual 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.

GENERALIDADES.

-Fue escrito y desarrollado por Joseph Kruskal, publicado por primera vez en Proceedings of the american Mathmatical Society en 1956.

Es un algoritmo voraz, sirve para encontrar el arbol de expansion minimo en un grafo conexo y ponderados.

ARBOL DE EXPANSION

Es un arbol compuestos por todos los vertices y algunas de las aristas en el cual no existiran ciclos.

ARBOL DE EXPANSION MINIMA

Es en el cual no existiran ciclos en donde la suma de sus aristas es la de menor peso .

ALGORITMO DE KRUSKAL

El algoritmo consiste en buscar el arbol de expansion minima.Se busca el arco de menor peso y se une los vertices siempre y cuando no se forme un ciclo .Esto se hace asta que todos los vertices esten comprendidos en el arbol .Para comprobar que el arbol de expansion minimo este hecho se revisa que el numero de aristas este igual al numero de vertices -1

EJEMPLOS