Un algoritmo para la realización de grafos con las actividades en los arcos -grafos pert-

Abstract

El problema de dibujar redes con las actividades en los arcos (redes PERT) es un problema NP-completo. Diferentes autores (Syslo, 1984) han establecido límites al mismo. En primer lugar debemos diferenciar entre redes con actividades en los nudos y redes con actividades en los arcos. Si las actividades están en los nudos, el dibujo de la red es muy fácil, pero cuando las actividades están en los arcos, generalmente es necesaria la utilización de actividades ficticias para mantener de forma correcta las relaciones entre las actividades. En este artículo se propone un sencillo y didáctico algoritmo para el caso de un pequeño número de nodos donde es necesario un algoritmo intuitivo. En el algoritmo se definen cuatro tipos diferentes de nodos que pueden aparecer en el grafo, permitiéndonos identificar las actividades ficticias tal y como se muestra en un ejemplo.