ALGORITMO DE PRIM

HISTORIA

ROBERT C. PRIM

En 1941 se licenció en ingeniería eléctrica 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.

En plena Segunda Guerra Mundial, 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

¿COMO LLEGO PRIM A ESTE ALGORITMO?

Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956.

REQUISITOS PARA SU FUNCIONAMIENTO

Ser un grafo conexo

ser un grafo sin ciclos

tener todos los arcos etiquetados

¿COMO FUNCIONA ?

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

PASOS PARA APLICARLO

La idea básica consiste en añadir en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente :

Paso 1: se elige un vértice u de G y se considera el árbol s= {u}

Paso 2: se considera la arista e de mínimo peso que une un vértice de s y un vértice que no es de s y se hace s=s+se

Paso 3: si el n° de aristas de t es n-1 el algoritmo termina. En caso contrario se vuelve al paso

EJEMPLO