ALGORITMO DE KRUSKAL

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.
Investigador del MathCenter (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 originalmentepor Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sinciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices onodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.
La aplicación típica de este problema es el diseño deredes 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 tarifasdiferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.
https://es.wikipedia.org/wiki/Joseph_Kruskal

árbol de coste mínimo
dado un grafo G con nodosconectados por arcos con peso (coste o longitud): el peso o coste total de un árbol será la suma de pesos de sus arcos. Obviamente, arboles diferentes tendrán un coste diferente. El problema esentonces, ¿Cómo encontrar el árbol de coste minimo?
Una manera de encontrar la solución al problema del árbol de coste total minimo, es la numeración completa. Aunque esta forma de resolución es eficaz, nose puede considerar un algoritmo, y además no es nada eficiente.
Este problema fue resuelto independientemente por Kruskal (1956) y la existencia de un algoritmo polinomial es una grata sorpresa,...