Data Structures and Algorithms MCQ - Graph Algorithm

6 Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements:
I. No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D).
II. For every edge (u, v) of G, if u is at depth i and u is at depth j in TB, then |i – j | = 1.
Which of the statements above must necessarily be true?

Statement (i) is true.
(i) No edges of G is a cross edge with respect to T_D.

7 Lt G be an undirected graph. Consider a depth first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

In DFS if ‘v’ is visited after ‘u’ then one of the following is true.
(i) if (u, v) is an edge

(ii) if ‘u’ is x leaf node

8 Consider the following graph

Among the following sequences
1. abeghf
2. abfehg
3. abfhge
4. afghbe
Which are depth first traversals of the above graph?

(1) a b e g h f
(3) a b f h g e
(4) a f g h b e is possible DFS of given graph.

9 In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

If n vertex and K edges are there then the number of connected component in the graph is n – K.

10 Let T be a depth first search tree in a undirected graph G. Vertices-u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

For the above graph, conducting depth First scarch:
Stack : A
Stack : DBC Tree : A
Stack : EBC Tree : A / D
Stack : BC Tree : A / D / E
Stack : BC
Stack : Φ Tree :

Considering l eaf nodes E and C, t he gi ven condition is satisfied as their degrees are more than one. But none of (A), (B) or (C) hold.
But a cycle consisting of E and all its neighbour hold.

Data Structures and Algorithms MCQ - Graph Algorithm

Graph Algorithms Questions for UGC NET Computer Science

Graph Algorithms MCQ

Graph Algorithms Multiple choice questions

Accessibility

Status
Q	M	N	O	P	R
2	1	1		1
2	2	1		1	1
2	2	2	1	1	1