2022-147

Consider the Active Time Diagram defined below. The rows, \( a \) to \( e \), represent the nodes of a network. The columns, 1 to 10, represent the star and ending times of the nodes during a given DFS Algorithm, which starts at node \( a \) and proceeds through the network. So, the horizontal bar at row \( a \) indicates that node \( a \) has starting time 1 and ending time 10, delimiting the time it is active, and so on for the others.

Based on this diagram, we are able to infer some information on Edge Classification, as follows:

1. Edges \( d \rightarrow c \) and \( e \rightarrow d \) are cross-edges.
2. Edges \( a \rightarrow c \) and \( a \rightarrow e \) are forward-edges.
3. Edge \( c \rightarrow a \) is a backward-edge.

Given the above statements, which of them are true:

1. I and II.
2. I and III.
3. II and III.
4. I, II and III.
5. None of the above.

Original idea by: Fábio Assunção.