Algoritmo ejemplo paso a paso.
Dado el grafo (1) determinamos su matriz de precedencia (2)
Recuerde que el 1 en a intersección de a fila A con la columna B significa "A es padre de B" o bien "B es hijo de A".
A continuación contamos los hijos que tiene cada padre (3). Observamos que B no tiene hijos (4). Esto o indica el 0 en la fila B, por lo tanto o indicamos colocando a B encabezando la primera columna auxiliar.
Tachamos todos los arcos que llegan a B (5), lo que se puede observar gráficamente (6) y (7) y no le prestamos más atención a B (guiones a continuación del 0. Gráficamente tenemos (8).
Contamos nuevamente hijos y anotamos aquellos nodos que no tienen (9). Tachamos con el mismo criterio que en el paso anterior. Gráficamente (10) y (11). Por lo tanto no le prestamos más atención a A y a D. (11) y (12)
Contamos nuevamente hijos y anotamos aquellos nodos que no tienen (13). Tachamos con el mismo criterio que en el paso anterior. Gráficamente (14) y (15). Por lo tanto no le prestamos más atención a E. (15) y (16)
Contamos nuevamente hijos y anotamos aquellos nodos que no tienen (17). Tachamos con el mismo criterio que en el paso anterior. Gráficamente (18) . Por lo tanto no le prestamos más atención a C. (19) . (!!!)
Con lo cual ya no tenemos más para averiguar. Debemos entonces reconstruir el grafo, ordenándolo por niveles. Debemos recordar en qué orden fuimos eliminando los nodos (20)
Luego, irán en último término aquellos que no tienen hijos y así sucesivamente (21)
A continuación debemos recordar nuestra matriz de precedencia (22) para trazar los arcos (23)
Y entonces obtener el resultado final (24)
Ejemplo dado durante el curso:
a. Controle que la red mostrada concuerde con la matriz
b. Ordene por niveles de acuerdo al nuevo criterio explicado
En este caso el grafo es realizable, consígalo de esta manera.
Para el primer criterio utilice el siguiente esquema, para el segundo criterio defínalo Ud. mismo. Luego saque conclusiones sobre las redes obtenidas.
Aplique el criterio de ordenamiento por niveles a los grafos obtenidos cuando se estudió matriz de precedencia. En caso de aparecer dificultades de aplicación, justifíquelas.