Algoritmo de Kruskal 

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. 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. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Funciona de la siguiente manera:

• se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
• se crea un conjunto C que contenga a todas las aristas del grafo
• mientras C es no vacío
  • eliminar una arista de peso mínimo de C
  • si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
  • en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito porJoseph Kruskal.

Joseph Kruskal. 

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óncombinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

Algoritmo de Kruskal,[en linea]:http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal, 09 de septiembre de 2012, México D.F.

Joseph Kruskal, [en linea]:http://es.wikipedia.org/wiki/Joseph_Kruskal, 09 de septiembre de 2012, México D.F

[Algoritmo de Kruskal]. Recuperado de: http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/220px-Minimum_spanning_tree.svg.png, 09 de septiembre de 2012, México D.F.