Question 1 |
Which of the follwing is/are TRUE?
S1: In a weighted undirected graph G = (V, E, w), breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in O(V + E) time.
S2: In a weighted undirected tree G = (V, E, w), breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in O(V + E) time.
S1: In a weighted undirected graph G = (V, E, w), breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in O(V + E) time.
S2: In a weighted undirected tree G = (V, E, w), breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in O(V + E) time.
S1 is TRUE and S2 is FALSE | |
S1 is FALSE and S2 is TRUE | |
S1 and S2 are TRUE | |
S1 and S2 are FALSE |
Question 1 Explanation:
S1 is FALSE
Only in unweighted graphs.
S2 is TRUE
True. In a tree, there is only one path between two vertices, and breadth-first search finds it.
Click to Join Our Telegram Group for Latest Update of MOCK TEST 
Click Here to Practice ALL Previous MOCK TEST FREE
Only in unweighted graphs.
S2 is TRUE
True. In a tree, there is only one path between two vertices, and breadth-first search finds it.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 2 |
Which of the follwing is/are TRUE?
S1: The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.
S2: In an unweighted graph where the distance between any two vertices is at most T, any BFS tree has depth at most T, but a DFS tree might have larger depth.
S1: The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.
S2: In an unweighted graph where the distance between any two vertices is at most T, any BFS tree has depth at most T, but a DFS tree might have larger depth.
S1 is TRUE and S2 is FALSE | |
S1 is FALSE and S2 is TRUE | |
S1 and S2 are TRUE | |
S1 and S2 are FALSE |
Question 2 Explanation:
S1 is TRUE
Since BFS finds paths using the fewest number of edges, the BFS depth of any vertex is at least as small as the DFS depth of the same vertex. Thus, the DFS tree has a greater or equal depth.
S2 is TRUE
TRUE. Since all vertices are connected by a path with at most T edges, and since BFS always finds the path with the fewest edges, the BFS tree will have depth at most T. A DFS tree may have depth up to V-1 (for example, in a complete graph).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Since BFS finds paths using the fewest number of edges, the BFS depth of any vertex is at least as small as the DFS depth of the same vertex. Thus, the DFS tree has a greater or equal depth.
S2 is TRUE
TRUE. Since all vertices are connected by a path with at most T edges, and since BFS always finds the path with the fewest edges, the BFS tree will have depth at most T. A DFS tree may have depth up to V-1 (for example, in a complete graph).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 3 |
Which of the follwing is/are TRUE?
S1: Suppose we do a DFS on a directed graph G. If we remove all of the back edges found, the resulting graph is now acyclic.
S2: For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic.
S1: Suppose we do a DFS on a directed graph G. If we remove all of the back edges found, the resulting graph is now acyclic.
S2: For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic.
S1 is TRUE and S2 is FALSE | |
S1 is FALSE and S2 is TRUE | |
S1 and S2 are TRUE | |
S1 and S2 are FALSE |
Question 3 Explanation:
S1 is TRUE
If DFS finds no back edges, then the graph is acyclic. Removing any back edges found doesn't change the traversal order of DFS, so running DFS again on the modified graph would produce no back edges.
S2 is FLASE
It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level)
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
If DFS finds no back edges, then the graph is acyclic. Removing any back edges found doesn't change the traversal order of DFS, so running DFS again on the modified graph would produce no back edges.
S2 is FLASE
It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level)
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 4 |
Perform a depth-first search on the following graph starting at A. Label every edge in
the graph with T if it's a tree edge, B if it's a back edge, F if it's a forward edge, and
C if it's a cross edge.
Which of the following is true for B,F and C?
NOTE: Whenever faced with a decision of which node to pick from a set of nodes, pick the node whose label occurs earliest in the alphabet.
Which of the following is true for B,F and C?
NOTE: Whenever faced with a decision of which node to pick from a set of nodes, pick the node whose label occurs earliest in the alphabet.
B : {(E,C)}, C : {(E,C),(C,G)}, F : {(E,G)} | |
B : {(C,A)}, C : {(F,C)}, F : {(E,G),(F,G)} | |
B : {(C,A)}, C : {(F,C),(F,G)}, F : {(E,G)} | |
B : {(C,A)}, C : {}, F : {(E,G),(F,C),(F,G)} |
Question 4 Explanation:
Tree Edge: It is an edge which is present in the tree obtained after applying DFS on the graph.
Forward edge: (u, v), where v is a descendant of u, but not a tree edge .It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
Back edge: (u, v), where v is a ancestor of u, but not a tree edge. It is a non-tree edge that connects a vertex to ancestor in a DFS-tree.
Cross Edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them in DFS Tree. Reference : https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf
MIT faculty Video Reference
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 5 |
Which of the following statements is/are correct?
S1 : If a depth-first search on a directed graph G = (V, E) produces exactly one back edge, then it is possible to choose an edge e \in E such that the graph G'= (V, E - {e}) is acyclic.
S2 : If a directed graph G is cyclic but can be made acyclic by removing one edge, then a depth-first search in G will encounter exactly one back edge.
S1 : If a depth-first search on a directed graph G = (V, E) produces exactly one back edge, then it is possible to choose an edge e \in E such that the graph G'= (V, E - {e}) is acyclic.
S2 : If a directed graph G is cyclic but can be made acyclic by removing one edge, then a depth-first search in G will encounter exactly one back edge.
S1 is True and S2 is False | |
S1 is False and S2 is True | |
S1 and S2 are False | |
S1 and S2 are True |
Question 5 Explanation:
S1 is TRUE.
Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has at least one back edge).
Notice that a graph can have two cycles but a single back edge, thus removing some edge that disrupts that cycle is insufficient, you have to remove specifically the back edge.
For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (a, c), (c, a)}), there are two cycles [a, b, c, a] and [a, c, a], but only one back edge (c, a). Removing edge (b, c) disrupts one of the cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains, [a, c, a]
S2 is FALSE
You can have multiple back edges, yet it can be possible to remove one edge that destroys all cycles. For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (b, a), (c, a)}), there are two cycles ([a, b, a] and [a, b, c, a]) and a DFS from a in G returns two back edges ((b, a) and (c, a)), but a single removal of edge (a, b) can disrupt both cycles, making the resulting graph acyclic.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has at least one back edge).
Notice that a graph can have two cycles but a single back edge, thus removing some edge that disrupts that cycle is insufficient, you have to remove specifically the back edge.
For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (a, c), (c, a)}), there are two cycles [a, b, c, a] and [a, c, a], but only one back edge (c, a). Removing edge (b, c) disrupts one of the cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains, [a, c, a]
S2 is FALSE
You can have multiple back edges, yet it can be possible to remove one edge that destroys all cycles. For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (b, a), (c, a)}), there are two cycles ([a, b, a] and [a, b, c, a]) and a DFS from a in G returns two back edges ((b, a) and (c, a)), but a single removal of edge (a, b) can disrupt both cycles, making the resulting graph acyclic.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
There are 5 questions to complete.
Suggested Mock Test For You.
ALL FREE Mock Test of GATE CSE