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: 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 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
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
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.
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
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. 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.