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 , where is the finite set of vertices and is the set of directed edges between the vertices. may contain cycles but there is no self-loop. Further, may not be strongly connected. Let be the graph obtained by reversing the directions of all the edges in without changing the set of vertices. Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex of a graph visits only the reachable vertices from in that graph. Which of the following statements must always be true, regardless of the structure of ?
Pick an option to check your answer. In a mock test a wrong answer here costs 2/3 mark.