GATE CS 2021 Set 2 Q46 — Minimum Spanning Trees

To analyze the given directed graph, we identify its cycles and connectivity structure:

• Option A (Correct): A directed graph has a topological order if and only if it is a Directed Acyclic Graph (DAG). Since this graph contains cycles (for example, $S \to A \to B \to S$), it is not a DAG, and therefore does not have a topological order.
• Option B (Correct): Let us perform a Depth-First Search (DFS) starting at vertex $S$:
  1. Start at $S$, move to $A$, then to $B$. From $B$, the edge $B \to S$ points back to the active ancestor $S$, which is the first back edge.
  2. Backtrack to $S$, then move to $C$, and then to $D$. From $D$, the edge $D \to C$ points back to the active ancestor $C$, which is the second back edge.
  3. From $D$, move to $F$, and then to $E$. From $E$, the edge $E \to F$ points back to the active ancestor $F$, which is the third back edge.
  Any DFS traversal starting at $S$ classifies exactly $3$ back edges.
• Option C (Incorrect): Every directed graph has at least one strongly connected component (SCC). Here, the SCCs are $\{S, A, B\}$, $\{C, D\}$, and $\{E, F\}$.
• Option D (Incorrect): The graph is not strongly connected. For instance, there is no directed path from $C$ to $S$.