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...
EXAM MAP
Medical
NEET