PERT 05

9 actividades, 7 ficticias sin simplificar frente a 2

Enunciado

Un método sistemático para dibujar el grafo PERT consiste en dar a cada actividad su propio nodo de inicio y de fin y unir con una ficticia cada prelación. El resultado es correcto, pero tiene muchas más ficticias de las necesarias. Considere el cuadro de prelaciones adjunto.

  1. Dibuje el grafo PERT por el método sistemático (sin fusionar nodos). ¿Cuántas ficticias tiene?
  1. Simplifíquelo: una ficticia puede eliminarse fusionando sus dos nodos cuando al hacerlo no se crea ninguna prelación nueva ni desaparece ninguna, no se juntan dos arcos entre los mismos nodos y el grafo sigue teniendo un único origen y un único final. ¿Cuántas ficticias quedan?
  1. Compruebe que ambos grafos tienen el mismo cuadro de ancestros y las mismas rutas (sin ficticias).
Tabla 1: Cuadro de prelaciones del enunciado
predecessor
activity
A ---
B ---
C ---
D A,C
E B
F D,E
G F
H F
I G,H

Resolución

Apartado 1

  1. Dibuje el grafo PERT por el método sistemático (sin fusionar nodos). ¿Cuántas ficticias tiene?
Figura 1: Grafo PERT sin simplificar

El grafo sin simplificar tiene 14 nodos y 7 ficticias: @10→12, @11→12, @13→14, @2→6, @4→6, @5→8, @7→8.

Apartado 2

  1. Simplifíquelo: una ficticia puede eliminarse fusionando sus dos nodos cuando al hacerlo no se crea ninguna prelación nueva ni desaparece ninguna, no se juntan dos arcos entre los mismos nodos y el grafo sigue teniendo un único origen y un único final. ¿Cuántas ficticias quedan?

La librería aplica exactamente esas reglas (simplify): recorre las ficticias y contrae las que pueden contraerse sin alterar las prelaciones distantes ni la estructura.

Figura 2: Grafo PERT simplificado

Tras simplificar quedan 9 nodos y 2 ficticias: @3→4, @7→8. Se han eliminado 5.

Las ficticias que quedan son las que transmiten una prelación que no puede expresarse compartiendo nodos: cada una une el final de un grupo de actividades con el inicio de otro grupo que depende de ellas y de otras más.

Apartado 3

  1. Compruebe que ambos grafos tienen el mismo cuadro de ancestros y las mismas rutas (sin ficticias).
Mismo cuadro de ancestros: True
Mismas rutas: True (6 rutas)