GATE CSE 2006 | Graphs Question 19 | Data Structures

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units      f(P) = 12 units
d(Q) = 6 units      f(Q) = 10 units
d(R) = 14 unit      f(R) = 18 units
Which one of the following statements is TRUE about the graph

There is only one connected component

There are two connected components, and P and R are connected

There are two connected components, and Q and R are connected

There are two connected components, and P and Q are connected

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let T be a depth first search tree in an 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?

There must exist a vertex w adjacent to both u and v in G

There must exist a vertex w whose removal disconnects u and v in G

There must exist a cycle in G containing u and v

There must exist a cycle in G containing u and all its neighbours in G.

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let T be a depth-first search tree in an 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?

There must exist a vertex w adjacent to both u and v in G

There must exist a vertex w whose removal disconnects u and v in G

There must exist a cycle in G containing u and v

There must exist a cycle in G containing u and all its neighbors in G.

GATE CSE 2001

MCQ (Single Correct Answer)

-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?

d(r, u) < d(r, v)

d(r, u) > d(r, v)

d(r, u)$$ \le $$d(r, v)

None of the above

PREVIOUS NEXT