Posibles caminos entre puntos de la red

Question

En mi curso de Gestión de Operaciones, se nos da un conjunto de nodos en un gráfico $\{A,B,C,D,E,F,G,H,I\}$ y se les da un conjunto de nodos predecesores, es decir, los nodos que preceden inmediatamente al nodo dado en el grafo como $\{NULL, A, A, B, C, (D,E), (D,E), F, G\}$ . Es decir, nada precede inmediatamente a A, pero A precede inmediatamente a B, y D y E preceden inmediatamente a F.

Mi pregunta es: Sin dibujar un grafo, ¿es posible averiguar los caminos que conectan el nodo $A$ al nodo $I$ ? Se nos dice que hay 4 caminos.

Gracias.

Answer 1

Mi estrategia era trabajar al revés. I debe ser precedida por G, G puede ser precedida por D o E, por lo que necesita dos casos posibles. En este punto, mi cuadro es el siguiente $$\frac{D}{E}GI$$ Entonces D sólo puede ser precedido por B, que sólo puede ser precedido por A, y E sólo puede ser precedido por C, que sólo puede ser precedido por A. Como hemos llegado a la raíz en todos los casos, hemos terminado. El cuadro es el siguiente $$\frac{ABD}{ACE}GI$$

De ahí se deduce que los dos caminos posibles son ABDGI y ACEGI,

Answer 2

Puede intentar la primera búsqueda en profundidad

$$\begin{align}-&A& A& B& C&~ (D,E)& (D,E)& F& G \\ A~ & B & C & D~~ & E~ & F~ & G&H~~&I \end{align}$$

> From A  two edges, to B and C  (C, B)   
    From B  one edge, to D (C, D)
      From D two edges, to F and G (C, F, G)
        From G one edge, to I (C, F)  ****
        From F one edge, to H (C)
    From C, one edge, to E (E)
      From E two edges, to F and G (F, G)
        From G one edge, to I (F) ****
        From F one edge, to H

That means there only two paths from A to I:  
A->B->D->G->I  
A->C->E->G->I