# Graphs · Data Structures · GATE CSE

Start Practice## Marks 1

GATE CSE 2016 Set 2

Breadth First Search $$(BFS)$$ is started on a binary tree beginning from the root vertex. There is a vertex $$t$$ at a distance four from the root. I...

GATE CSE 2016 Set 1

Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is ________________....

GATE CSE 2014 Set 1

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the
running time of Depth First Search on G, when G is represented a...

GATE CSE 2014 Set 3

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only...

GATE CSE 2014 Set 2

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected,
undirected graph. The tree T formed by the tree arcs is a ...

GATE CSE 2004

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

GATE CSE 2003

Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e
What are depth first t...

## Marks 2

GATE CSE 2020

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$...

GATE CSE 2018

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.$$ Co...

GATE CSE 2018

Let $$G$$ be a graph with $$100!$$ vertices, with each vertex labelled by a distinct permutation of the numbers $$1,2, … , 100.$$ There is an edge bet...

GATE CSE 2016 Set 2

In an adjacency list representation of an undirected simple graph $$G = (V,E),$$ each edge $$(u, v)$$ has two adjacency list entries: $$[v]$$ in the a...

GATE CSE 2015 Set 1

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest dista...

GATE CSE 2015 Set 3

Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the w...

GATE CSE 2012

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be th...

GATE CSE 2010

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j}
$$$W = \left( {\mat...

GATE CSE 2010

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j}
$$$W = \left( {\mat...

GATE CSE 2008

Consider the following sequence of nodes for the undirected graph given below.
1.a b e f d g c
2.a b e f c g d
3.a d g e b c f
4.a d b c g e f
A ...

GATE CSE 2007

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

GATE CSE 2006

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

GATE CSE 2006

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

GATE CSE 2006

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

GATE CSE 2001

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 o...

GATE CSE 2001

How many undirected graphs (not necessarily connected) can be constructed out
of a given set V = { v1,v2,........,vn } of n vertices?...

GATE CSE 2000

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 le...