1

GATE CSE 2001

MCQ (Single Correct Answer)

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

2

GATE CSE 2001

MCQ (Single Correct Answer)

+2

-0.6

How many undirected graphs (not necessarily connected) can be constructed out
of a given set V = { v

_{1},v_{2},........,v_{n}} of n vertices?3

GATE CSE 2000

MCQ (Single Correct Answer)

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

Questions Asked from Graphs (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages