GATE CSE 2021 Set 2 Q46

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.

Accepted Answer

Official answer: 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.. Explanation: Let us analyze each statement based on standard graph theory and traversal properties: 1. Topological Order (Option A): A directed graph has a topological ordering if and only if it is a Directed Acyclic Graph (DAG). The given graph contains directed cycles (for example, the cycle formed by vertices in the grid). Since it contains at least one cycle, it is not a DAG, and therefore does not have a topological order. Hence, Option A is correct. 2. Back Edges in DFS (Option B): A depth-first traversal starting from vertex S reaches all 16 vertices. In any DFS tree of this graph, the DFS tree contains 15 tree edges. Out of the remaining non-tree edges encountered during traversal, exactly 3 directed edges point from a descendant to an ancestor, which classifies them as back edges (corresponding to the fundamental cycles). Thus, Option B is correct. 3. Strongly Connected Component (Option C): Every directed graph has at least one strongly connected component (SCC) (trivially, even single vertices are SCCs if there are no larger ones, and here non-trivial SCCs exist as well). Thus, the statement that the graph does not have an SCC is false. Hence, Option C is incorrect. 4. Strong Connectivity of the Entire Graph (Option D): For each pair of vertices u and v to have a directed path between them, the entire graph would need to be strongly connected. Since the graph is not strongly connected (for instance, the top-right vertices have no path back to S), this statement is false. Hence, Option D is incorrect. Therefore, the correct options are A and B.

Answer

A) The graph does not have a topological order.

Answer

B) A depth-first traversal starting at vertex S classifies three directed edges as back edges.

Answer

C) The graph does not have a strongly connected component.

Answer

D) For each pair of vertices u and v, there is a directed path from u to v.

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

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 2

More on Graph Traversals

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

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 2

More on Graph Traversals

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

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 2

More on Graph Traversals

Share this solution

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

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 2

More on Graph Traversals

Share this solution