1
GATE CSE 2001
+2
-0.6
Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?
A
d(r, u) < d(r, v)
B
d(r, u) > d(r, v)
C
d(r, u)$$\le$$d(r, v)
D
None of the above
2
GATE CSE 2001
+2
-0.6
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v1,v2,........,vn } of n vertices?
A
$$\frac{n(n-1)} {2}$$
B
2n
C
n!
D
$$2^\frac{n(n-1)} {2}$$
3
GATE CSE 2000
+2
-0.6
Let 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?
A
{u, v} must be an edge in G, and u is a descendant of v in T
B
{u, v} must be an edge in G, and v is a descendant of u in T
C
If {u, v} is not an edge in G then u is a leaf in T
D
If {u, v} is not an edge in G then u and v must have the same parent in T
GATE CSE Subjects
EXAM MAP
Medical
NEET