topic – RBR

Question 1

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. Consider the following statements.

_D

_B

Which of the statements above must necessarily be true?

A	I only
B	II only
C	Both I and II
D	Neither I nor II

Data-Structures Graphs Gate 2018

Question 1 Explanation:

I. Undirected graph do not have cross edges in DFS. But can have cross edges in directed graph. Hence True.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here |i - j| = |1 - 1| = 0. Hence, False.

Question 2

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

G

A	P only
B	Q only
C	Neither P nor Q
D	Both P and Q

Data-Structures Graphs 2016 set-01

Question 2 Explanation:

Given undirected weighted graph with distinct positive edges.
Every edge weight is increased by the same value say,

P: Minimum Spanning Tree will not change ABC in both the cases.
Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).

Question 3

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry W_ij in the matrix W.

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is _________.

A	12
B	13
C	14
D	15

Data-Structures Graphs 2016 set-01

Question 3 Explanation:

Let vertices be A, B, C and D.
x directly connects C to D.
The shortest path (excluding x) from C to D is of weight 12 (C-B-A-D).

Question 4

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 adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?

A	Θ(n²)
B	Θ(n+m)
C	Θ(m²)
D	Θ(n⁴)

Data-Structures Graphs GATE 2016 set-2

Question 4 Explanation:

Applying BFS on Undirected graph give you twin pointer.
Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

Question 5

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 as an adjacency matrix?

A	θ(n)
B	θ(n+m)
C	θ(n² )
D	θ(m² )

Data-Structures Graphs GATE 2014(Set-01)

Question 5 Explanation:

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V²).

Question 6

Consider the directed graph given below.

Which one of the following is TRUE?

A	The graph does not have any topological ordering.
B	Both PQRS and SRQP are topological.
C	Both PSRQ and SPRQ are topological orderings.
D	PSRQ is the only topological ordering.

Data-Structures Graphs GATE 2014(Set-01)

Question 6 Explanation:

There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.

Question 7

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 data structure for computing

A	the shortest path between every pair of vertices.
B	the shortest path from W to every vertex in the graph.
C	the shortest paths from W to only those nodes that are leaves of T.
D	the longest path in the graph.

Data-Structures Graphs Gate 2014 Set -02

Question 7 Explanation:

One of the application of BFS algorithm is to find the shortest path between nodes u and v.
But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

Question 8

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 after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

A	19
B	20
C	21
D	22

Algorithms Graphs Gate 2014 Set -03

Question 8 Explanation:

Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.

Question 9

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

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

A	7
B	8
C	9
D	10

Data-Structures Graphs 2010

Question 9 Explanation:

The MST will be 1---3---4---0 => cost = 4+2+4 = 10

Question 10

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

A	θ(n)
B	θ(m)
C	θ(m+n)
D	θ(mn)

Data-Structures Graphs Gate-2008

Question 10 Explanation:

To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n²).

Question 11

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

A	MNOPQR
B	NQMPOR
C	QMNPRO
D	QMNPOR

Data-Structures Graphs Gate-2008

Question 11 Explanation:

Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).

Question 12

G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

A	For every subset of k vertices, the induced subgraph has at most 2k–2 edges
B	The minimum cut in G has at least two edges
C	There are two edge-disjoint paths between every pair to vertices
D	There are two vertex-disjoint paths between every pair of vertices

Data-Structures Graphs Gate-2008

Question 12 Explanation:

→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 =2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).

Question 13

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

A	I and III only
B	II and III only
C	II, III and IV only
D	I, II and III only

Data-Structures Graphs Gate 2008-IT

Question 13 Explanation:

I) After visiting 'f', 'c' or 'g' should be visited next. So, the traversal is incorrect.
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.

Question 14

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

A	1 2 3 4 5 6
B	1 3 2 4 5 6
C	1 3 2 4 6 5
D	3 2 4 1 6 5

Data-Structures Graphs Gate-2007

Question 14 Explanation:

The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.

Question 15

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?

A	d[u] < d[v]
B	d[u] < f[v]
C	f[u] < f[v]
D	f[u] > f[v]

Data-Structures Graphs Gate 2007-IT

Question 15 Explanation:

Option A:
d[u] Option B:
d[u] Option C:
f[u] So, option D is True.

Question 16

Let T be a depth first search tree in an undirected graph G. Vertices u and n 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?

A	There must exist a vertex w adjacent to both u and v in G
B	There must exist a vertex w whose removal disconnects u and v in G
C	There must exist a cycle in G containing u and v
D	There must exist a cycle in G containing u and all its neighbours in G

Data-Structures Graphs Gate-2006

Question 16 Explanation:

Very difficult assume a graphs here. So, As per the GATE key they given Option D is correct answer.

Question 17

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

A	{P, Q, R, S}, {T}, {U}, {V}
B	{P, Q, R, S, T, V}, {U}
C	{P, Q, S, T, V}, {R}, {U}
D	{P, Q, R, S, T, U, V}

Data-Structures Graphs Gate 2006-IT

Question 17 Explanation:

In a strongly connected component every two vertices must be reachable from one to other and itis maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.

Question 18

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

A	There is only one connected component
B	There are two connected components, and P and R are connected
C	There are two connected components, and Q and R are connected
D	There are two connected components, and P and Q are connected

Data-Structures Graphs Gate 2006-IT

Question 18 Explanation:

Since, d(q) = d(p) + 1 and f(q) < f(p) which means p and q are connected and r is separate, so (D) is the answer.

Question 19

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?

A	Graph G has no minimum spanning tree (MST)
B	Graph G has a unique MST of cost n-1
C	Graph G has multiple distinct MSTs, each of cost n-1
D	Graph G has multiple spanning trees of different costs

Data-Structures Graphs Gate-2005

Question 19 Explanation:

From given data, we can say that the given graph is complete graph with all edge weights 1. Hence weight of MST is n-1.
Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n-1).

Question 20

Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y The edge e must definitely belong to:

A	the minimum weighted spanning tree of G
B	the weighted shortest path from s to t
C	each path from s to t
D	the weighted longest path from s to t

Data-Structures Graphs Gate-2005

Question 20 Explanation:

Since every edge has distinct edge weights. So, the edge with minimum weight will definitely be present in MST.

Question 21

Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

A	a path from s to t in the minimum weighted spanning tree
B	a weighted shortest path from s to t
C	an Euler walk from s to t
D	a Hamiltonian path from s to t

Data-Structures Graphs Gate-2005

Question 21 Explanation:

Let us first understand what is minimum congestion actually.
Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.

Question 22

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

i = 0
do {
    j = i + 1;
    while ((j < n) && E1) 
       j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf ("Sink does not exist");

Choose the correct expressions for E₁ and E₂

A	E₁ : A[i][j] and E₂ : i = j;
B	E₁ : !A[i][j] and E₂ : i = j + 1;
C	E₁: !A[i][j] and E₂ : i = j;
D	E₁ : A[i][j] and E₂ : i = j + 1;

Theory-of-Computation Graphs Gate 2005-IT

Question 22 Explanation:

If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E₂, which makes rows slip when there is no edge from i to it, making it impossible for them to form a sink. This is done through
E₁: A[i][j]
and
E₂: i = j
E₁ makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink. Similarly, all previous j can also not be a sink. Now, the next potential candidate for sink is j. So, in E₂, we must make i = j.
So, answer is (C).

Question 23

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

i = 0
do {
    j = i + 1;
    while ((j < n) && E1) j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf("Sink does not exist");

Choose the correct expressions for E3

A	(A[i][j] && !A[j][i])
B	(!A[i][j] && A[j][i])
C	(!A[i][j] \| \| A[j][i])
D	(A[i][j] \| \| !A[j][i])

Theory-of-Computation Graphs Gate 2005-IT

Question 23 Explanation:

First go through the explanation of previous question.
Now, the loop breaks when we found a potential sink-that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix.
So, if the column in which this vertex comes is all 1's and the row is all 0's (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E₃ is checking this condition. But in the code flag is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.
So, the condition is E₃ must make flag = 0, if the found i is not a sink. So, the condition should be
A[i][j] | | !A[j][i]
So, option (D) is the answer.

Question 24

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.

A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

A
B
C
D

Theory-of-Computation Graphs Gate 2005-IT

Question 24 Explanation:

Question 25

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.

A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

A	>100 but finite
B	∞
C	3
D	>3 and ≤100

Theory-of-Computation Graphs Gate 2005-IT

Question 25 Explanation:

We consider ABDF at t, they are:
The distance between A and the nodes B, D, F respectively are:
t: 1 2 3
t + 1: 3 2 3
t + 2: 3 4 3
t + 3: 5 4 5
t + 4: 5 6 5
t + 5: 7 6 7
t + 6: 7 8 7
t + 7: 9 8 9
t + 8: 9 to 10
and this continues.
So, in every two steps they get incremented by 2.
So,
at t + 99, F is 101
at t + 100, F is 101.

Question 26

Level order traversal of a rooted tree can be done by starting from the root and performing

A	preorder traversal
B	in-order traversal
C	depth first search
D	breadth first search

Data-Structures Graphs Gate-2004

Question 26 Explanation:

Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

Question 27

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

Which are depth first traversals of the above graph?

A	I, II and IV only
B	I and IV only
C	II, III and IV only
D	I, III and IV only

Data-Structures Graphs Gate-2003

Question 27 Explanation:

I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)

Question 28

Let G (V, E) be a directed graph with n vertices. A path from v_i to v_j in G is sequence of vertices (v_i, v_i+1, ......., v_j) such that (vk, v_k+1) ∈ E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow

Consider the following algorithm.

for i = 1 to n
   for j = 1 to n
      for k = 1 to n
         A [j , k] = max (A[j, k] (A[j, i] + A [i, k]);

Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?

A	A[j,k] ≤ n
B	If A[j,j] ≥ n - 1, then G has a Hamiltonian cycle
C	If there exists a path from j to k, A[j,k] contains the longest path length from j to k
D	If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges

Algorithms Graphs Gate-2003

Question 28 Explanation:

Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.

Question 29

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

Data-Structures Graphs Gate-2000

Question 29 Explanation:

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.

Question 30

A	0
B	1
C	2
D	3

Data-Structures Graphs Gate-1999

Question 30 Explanation:

Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3

Question 31

Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true?

A	G has no cycles.
B	The graph obtained by removing any edge from G is not connected.
C	G has at least one cycle.
D	The graph obtained by removing any two edges from G is not connected.
E	Both C and D.

Algorithms Graphs Gate-1993

Question 31 Explanation:

If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3

Question 32

How many edges are there in a forest with p components having n vertices in all?

A

n-p

Data-Structures Graphs Gate-1992

Question 32 Explanation:

Forest is a graph with no cycle.
Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).
So, total of n-p edges for p components.

Question 33

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)
B	d(r,u)>d(r,v)
C	d(r,u)≤d(r,v)
D	None of the above

Data-Structures Graphs Gate-2001

Question 33 Explanation:

d(r,u) and d(r, v) will be equal when u and v are at same level, otherwise d(r,u) will be less than d(r,v).

Question 34

There is a linear-time algorithm for testing the planarity of finite graphs.

A	True
B	False

Data-Structures Graphs GATE-1987

Question 34 Explanation:

Yes, Linear time algorithm is there for testing the planarity of finite graphs.