Question

Consider the following directed graph: 
Which of the following is/are correct about the graph? 

• A. The graph does not have a topological order.
• B. A depth-first traversal starting at vertex \(S\) classifies three directed edges as back edges.
• C. The graph does not have a strongly connected component.
• D. For each pair of vertices \(u\) and \(v\), there is a directed path from \(u\) to \(v\).

Hint:

Cycles imply no topological order and guarantee the presence of back edges in DFS.

Answer 1

The Correct Option is A, B

Step 1: Check existence of a topological order.
A directed graph has a topological ordering if and only if it is acyclic. From the given diagram, there are directed cycles present in the graph. Hence, the graph is not a DAG and does not admit any topological order. Therefore, statement (A) is correct.

Step 2: DFS back edges from vertex \(S\).
In a depth-first search of a directed graph, a back edge indicates the presence of a cycle. Starting DFS from vertex \(S\), three edges are encountered that point to ancestors in the DFS tree, and hence are classified as back edges. Therefore, statement (B) is correct.

Step 3: Strongly connected components.
The presence of cycles implies that the graph contains at least one non-trivial strongly connected component. Hence, statement (C) is false.

Step 4: Reachability between all vertex pairs.
Although the graph has cycles, it is not the case that every vertex can reach every other vertex via directed paths. Hence, the graph is not strongly connected as a whole, and statement (D) is false.

Step 5: Conclusion.
Thus, the correct options are (A) and (B).