Question 1 |
Let U = \{1, 2, 3\}. Let 2^U denote the powerset of U. Consider an undirected graph
G whose vertex set is 2^U. For any A,B \in 2^U, (A,B) is an edge in G if and only
if (i) A \neq B, and (ii) either A \subseteq B or B \subseteq A. For any vertex A in G, the set of
all possible orderings in which the vertices of G can be visited in a Breadth First
Search (BFS) starting from A is denoted by B(A).
If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.
If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.
524 | |
63218 | |
5040 | |
2540 |
Question 1 Explanation:
Question 2 |
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
Root of T can never be an articulation point in G. | |
Root of T is an articulation point in G if and only if it has 2 or more children. | |
A leaf of T can be an articulation point in G. | |
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u. |
Question 2 Explanation:
Question 3 |
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
v2v4 | |
v1v4 | |
v4v5 | |
v3v4 |
Question 3 Explanation:
Question 4 |
Which of the following is application of Breath First Search on the graph?
Finding diameter of the graph | |
Finding bipartite graph | |
Both (A) and (B) | |
None of the above |
Question 4 Explanation:
Question 5 |
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.
Which of the statements above must necessarily be true?
(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.
Which of the statements above must necessarily be true?
I only | |
II only | |
Both I and II | |
Neither I nor II |
Question 5 Explanation:
There are 5 questions to complete.