GATE-2024-CS1(Forenoon)
March 23, 2025GATE-2024-CS1(Forenoon)
March 23, 2025GATE-2024-CS1(Forenoon)
| Question 45 |
Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are TRUE for every such graph G and tree T ?
| There are no back-edges in G with respect to the tree T | |
| There are no cross-edges in G with respect to the tree T | |
| There are no forward-edges in G with respect to the tree T | |
| The only edges in G are the edges in T |
Question 45 Explanation:
(A) Not True: Back edges are still possible in this scenario, as explained before.
(B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it’s not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T.
(C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G:
If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge).
If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant).
Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.
(B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it’s not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T.
(C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G:
If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge).
If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant).
Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.
Correct Answer: C
Question 45 Explanation:
(A) Not True: Back edges are still possible in this scenario, as explained before.
(B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it’s not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T.
(C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G:
If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge).
If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant).
Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.
(B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it’s not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T.
(C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G:
If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge).
If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant).
Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.