Skip to content
Q40Section DA (Data Science and Artificial Intelligence (Q11–Q65))40 of 65

Reachability relationship between a graph and its edge-reversed graph

Consider a directed graph G=(V,E)G = (V, E), where VV is the finite set of vertices and EE is the set of directed edges between the vertices. GG may contain cycles but there is no self-loop. Further, GG may not be strongly connected. Let GRG^R be the graph obtained by reversing the directions of all the edges in GG without changing the set of vertices. Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex vv of a graph visits only the reachable vertices from vv in that graph. Which of the following statements must always be true, regardless of the structure of GG?

Options

Pick an option to check your answer. In a mock test a wrong answer here costs 2/3 mark.