Algoritmo de PRIM

"Algoritmo de Prim"

Robert Prim Clay (nacido en 1921 en Sweetwater, Texas) es un matemático y científico informático. En 1941, Prim obtuvo su licenciatura en Ingeniería Eléctrica de la Universidad de Princeton. Más tarde, en 1949, él recibió su doctorado en matemáticas también. Prim Robert trabajó en la Universidad de Princeton desde 1948 hasta 1949 como investigador asociado. Durante el clímax de la Segunda Guerra Mundial (1941-1944), Prim trabajó como ingeniero de General Electric. Desde 1944 hasta 1949, fue contratado por el Laboratorio de los Estados Unidos artillería naval como ingeniero y un matemático más tarde. En los Laboratorios Bell, se desempeñó como director de las matemáticas de investigación de 1958 a 1961. No, el algoritmo de Prim  desarrollado. Después de los Laboratorios Bell, Prim se convirtió en vicepresidente de investigación de los Laboratorios Nacionales .Durante su carrera en los Laboratorios Bell, Robert Prim, junto con un compañero de trabajo José Kruskal desarrollado dos algoritmos diferentes para encontrar un árbol de expansión mínimo en un grafo ponderado, un bloque básico de tropiezo en el diseño de redes informáticas. Su algoritmo lleva su propio nombre, el algoritmo de Prim, fue descubierto originalmente en 1930 por el matemático Vojtech Jarnik y posteriormente de forma independiente por Prim en 1957. Fue redescubierto después por Edsger Dijkstra en 1959. A veces se conoce como el algoritmo DJP o algoritmo de Jarnik.

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

Por lo tanto, el Algoritmo de Prim debe su nombre al matemático Robert Prim Clay.

Referencias:

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

http://connect.in.com/robert-c-prim/biography-236601.html