Prelaciones 06

7 actividades, 6 nodos; numeración de los nodos

Enunciado

Considere el proyecto cuyo cuadro de prelaciones se adjunta. En un grafo PERT los nodos (sucesos) se numeran de modo que todo arco vaya de un número menor a uno mayor; esa numeración no es única.

  1. Dibuje el grafo PERT con el mínimo número de ficticias y numere sus nodos. Compruebe que cada arco \((i, j)\), ficticias incluidas, cumple \(i < j\).
  1. ¿Qué nodos pueden intercambiar su número sin violar la regla? Dé una segunda numeración válida.
  1. ¿Cuántas numeraciones válidas distintas admite el grafo? (Es el número de ordenaciones topológicas; cuéntelas con un programa.)
  1. ¿Por qué conviene que la numeración sea creciente a lo largo de los arcos? Piense en la matriz de Zaderenko.
Tabla 1: Cuadro de datos del enunciado
predecessor
activity
A ---
B ---
C ---
D B,C
E A,D
F B,C
G F

Resolución

Apartado 1

  1. Dibuje el grafo PERT con el mínimo número de ficticias y numere sus nodos. Compruebe que cada arco \((i, j)\), ficticias incluidas, cumple \(i < j\).
Figura 1: Grafo PERT con los nodos numerados
Tabla 2: Arcos del grafo: origen, destino y comprobación i < j
i j i < j
actividad
B 1 2 True
C 1 3 True
A 1 5 True
@2→3 2 3 True
F 3 4 True
D 3 5 True
G 4 6 True
E 5 6 True

La numeración de la librería cumple la regla en 8 de 8 arcos.

Apartado 2

  1. ¿Qué nodos pueden intercambiar su número sin violar la regla? Dé una segunda numeración válida.

Dos nodos pueden intercambiar su número cuando no hay ningún camino entre ellos (ninguno es antecesor del otro). Se comprueba con el grafo: el par \((u, v)\) es intercambiable si \(v\) no es alcanzable desde \(u\) ni \(u\) desde \(v\).

Pares de nodos intercambiables: [('4', '5')]

Intercambiando los nodos 4 y 5 todos los arcos siguen cumpliendo i < j: True.

i j i < j
actividad
B 1 2 True
C 1 3 True
A 1 4 True
@2→3 2 3 True
F 3 5 True
D 3 4 True
G 5 6 True
E 4 6 True

Apartado 3

  1. ¿Cuántas numeraciones válidas distintas admite el grafo? (Es el número de ordenaciones topológicas; cuéntelas con un programa.)

Las numeraciones válidas son las ordenaciones topológicas del grafo de sucesos. Se cuentan con programación dinámica sobre subconjuntos: el número de formas de ordenar un conjunto \(S\) es la suma, sobre cada nodo \(v\) de \(S\) sin antecesores dentro de \(S\), de las formas de ordenar \(S \setminus \{v\}\).

El grafo admite 2 numeraciones válidas distintas (una sola si cada nodo es antecesor o descendiente de todos los demás).

Tres de ellas (nodo de la librería → nuevo número), generadas con networkx:
   {'1': 1, '2': 2, '3': 3, '5': 4, '4': 5, '6': 6}
   {'1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6}

Apartado 4

  1. ¿Por qué conviene que la numeración sea creciente a lo largo de los arcos? Piense en la matriz de Zaderenko.

Con numeración creciente, la matriz de Zaderenko es triangular superior: cada arco está por encima de la diagonal, los tiempos tempranos se calculan recorriendo las columnas de izquierda a derecha y los tardíos las filas de abajo arriba, sin tener que buscar un orden de cálculo. Además, la regla garantiza que no hay ciclos.

Tabla 3: Matriz de Zaderenko (sin duraciones: X marca los arcos)
1 2 3 4 5 6
1 B C A
2 @2→3
3 F D
4 G
5 E
6