UN ALGORITMO PARA LA REALIZACIÓN DE GRAFOS CON LAS ACTIVIDADES EN LOS ARCOS –GRAFOS PERT–

Resumen

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. Palabras clave: redes PERT, actividades ficticias. Abstract When there are activities in the nodes, it is easy to draw the graph of the network. But when there are activities in the arcs, we generally need dummy activities to keep the relations between activities. In this paper we propose a simple and didactic algorithm with a small number of nodes where an intuitive algorithm is needed. There are four different types of nodes that could appear in the graph. They are used to identify the dummy activities as it is shown in the example. Key words: PERT networks, dummy activity.