Joseph Kruskal

*Nació el 29 de Enero de 1928 en Maplewood,Nueva Jersey.
*Murió el el 19 de Septiembre de 2010.
*Fue un matemático y estadístico estadounidense.

*Fue hermano del matemático y estadístico William Kruskal y del matemático-fisico Martín Kruskal (autor de las coordenadas de Kruskal) 

*En 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo. 

*El objetivo del algoritmo de Kruskal es construir un árbol(subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Algoritmo de Kruskal 

Es un algoritmo de la teoria de grafos  para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado.

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. 

 

INFORMACIÓN

Wikipedia(2009).Joseph.Kruskal.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Joseph_Kruskal

Wikipedia(2009).Algoritmo Kruskal.20 Abril 2015.Wikimedia Fundation.Inc sitio web:

http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal

IMAGEN

Joseph Kruskal recuperado de:

https://www.google.com.mx/search?q=joseph+kruska

Algoritmo de Kruskal recuperado de:

https://www.google.com.mx/search?q=algoritmo+de+kruskal