Fecha y lugar de nacimiento: En 1921, Sweetwater, Estados Unidos
Estudios: En 1941 se licenció en ingenieria electrica en la Universidad de Princeton. Más tarde, en 1949 recibe su doctorado en matemáticas en la misma universidad. Trabajó en dicha universidad desde 1948 hasta 1949 como investigador asociado.
Trabajos: Prim trabajó como ingeniero para General Electric. Desde 1944 hasta 1949 fue contratado por la United States Naval Ordnance Lab como ingeniero y más tarde como matemático. En los laboratorios Bell, trabajó como director de investigación matemática desde 1958 hasta 1961. Allí Prim desarrolló el conocido Algoritmo de Prim. Después de su estancia en los laboratorios Bell, Prim pasó a ser vicepresidente de investigación en Sandia National Laboratories
Conocido por: Durante su carrera en los laboratorios Bell, Robert Prim junto a su compañero Joseph Kruskal desarrolló dos algoritmos diferentes para encontrar los árboles abarcadores mínimos en un grafo ponderado. El algoritmo que lleva su nombre fue originalmente descubierto por el matemático Vojtech Jarnik y más tarde e independientemente por Prim en 1957.
Algoritmo de Prim
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 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
No hay comentarios:
Publicar un comentario