¿Quién inventó el Algoritmo de Prim?

¿Quién inventó el Algoritmo de Prim?

*Robert Prim Clay *

Robert Prim Clay (nacido en 1921 en Sweetwater , Texas, ) es un americano matemático y científico de la computación.

En 1941, Prim obtuvo su licenciatura en ingeniería eléctrica de la Universidad de Princeton . Más tarde, en 1949, recibió su Ph.D. en Matemáticas allí también. Prim Robert trabajó en la Universidad de Princeton desde 1948 hasta 1949 como investigador asociado.

Durante el apogeo de la Segunda Guerra Mundial (1941-1944), Prim trabajó como ingeniero para General Electric.

Desde 1944 hasta 1949, fue contratado por el Laboratorio de Artillería Naval de los Estados Unidos como un ingeniero y un matemático posterior.

En los Laboratorios Bell , se desempeñó como director de investigación de matemáticas 1958 a 1961. Allí, Prim desarrollo el algoritmo de Prim. Después de los Laboratorios Bell, Prim se convirtió en vicepresidente de investigación de los Laboratorios Nacionales Sandia.

Durante su carrera en los Laboratorios Bell, Robert Prim junto con un compañero de trabajo José Kruskal desarrollado dos algoritmos diferentes (ver algoritmo codicioso ) para encontrar un árbol de expansión mínimo en un promedio ponderado gráfico , un bloque básico de tropiezo en diseño por ordenador de la red. Su algoritmo propio nombre, el algoritmo de Prim, fue descubierto originalmente en 1930 por el matemático Vojtěch Jarnik más tarde y de forma independiente por Prim en 1957. Fue redescubierto después por Edsger Dijkstra en 1959. Se refiere a veces como el algoritmo DJP o el 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.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

Referencias:

v Significado de PRIM. [en línea]. < http://es.wikipedia.org/wiki/Algoritmo_de_Prim >. Consulta: Octubre, 2012
v  "Robert C. Prim." Wikipedia. Wikimedia Foundation, 22 Mar. 2012. Web. 09 Sept. 2012 <http://en.wikipedia.org/wiki/Robert_C._Prim> 

v Robert C. Prim. Digital image. N.p., n.d. Web. 9 Sept. 2012. <http://tinyurl.com/9ntfcgh>.