Graphs
Question 1 |
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
-
(I) No edge of G is a cross edge with respect to TD.
(A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then ∣i−j∣ = 1.
Which of the statements above must necessarily be true?
I only | |
II only | |
Both I and II | |
Neither I nor II |
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?
-
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
P only | |
Q only | |
Neither P nor Q | |
Both P and Q |
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 Wij 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 _________.
12 | |
13 | |
14 | |
15 |
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 efficient algorithm to set the twin pointer in each entry in each adjacency list?
Θ(n2) | |
Θ(n+m) | |
Θ(m2) | |
Θ(n4) |
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 |
θ(n) | |
θ(n+m) | |
θ(n2 ) | |
θ(m2 ) |
Question 6 |
The graph does not have any topological ordering. | |
Both PQRS and SRQP are topological. | |
Both PSRQ and SPRQ are topological orderings. | |
PSRQ is the only topological ordering. |

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 |
the shortest path between every pair of vertices. | |
the shortest path from W to every vertex in the graph. | |
the shortest paths from W to only those nodes that are leaves of T. | |
the longest path in the graph. |
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 |

19 | |
20 | |
21 | |
22 |

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

Question 9 |

7 | |
8 | |
9 | |
10 |
Question 10 |
θ(n) | |
θ(m) | |
θ(m+n) | |
θ(mn) |
Suppose if we are using Adjacency matrix means it takes θ(n2).
Question 11 |

MNOPQR
| |
NQMPOR
| |
QMNPRO
| |
QMNPOR |

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 |
For every subset of k vertices, the induced subgraph has at most 2k–2 edges | |
The minimum cut in G has at least two edges
| |
There are two edge-disjoint paths between every pair to vertices
| |
There are two vertex-disjoint paths between every pair of vertices |
> 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 |

I and III only | |
II and III only | |
II, III and IV only | |
I, II and III only
|
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.
Question 14 |

1 2 3 4 5 6 | |
1 3 2 4 5 6 | |
1 3 2 4 6 5 | |
3 2 4 1 6 5
|
(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 |
d[u] < d[v] | |
d[u] < f[v] | |
f[u] < f[v] | |
f[u] > f[v] |

Option A:
d[u]
d[u]
f[u]
Question 16 |
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 |
Question 17 |

{P, Q, R, S}, {T}, {U}, {V} | |
{P, Q, R, S, T, V}, {U} | |
{P, Q, S, T, V}, {R}, {U} | |
{P, Q, R, S, T, U, V} |
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.
Question 18 |
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 |
Question 19 |
Graph G has no minimum spanning tree (MST)
| |
Graph G has a unique MST of cost n-1
| |
Graph G has multiple distinct MSTs, each of cost n-1
| |
Graph G has multiple spanning trees of different costs
|
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 |
the minimum weighted spanning tree of G
| |
the weighted shortest path from s to t
| |
each path from s to t
| |
the weighted longest path from s to t
|
Question 21 |
a path from s to t in the minimum weighted spanning tree
| |
a weighted shortest path from s to t
| |
an Euler walk from s to t
| |
a Hamiltonian path from s to t
|
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 |
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");
E1 : A[i][j] and E2 : i = j; | |
E1 : !A[i][j] and E2 : i = j + 1; | |
E1: !A[i][j] and E2 : i = j; | |
E1 : A[i][j] and E2 : i = j + 1;
|
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 E2, 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
E1: A[i][j]
and
E2: i = j
E1 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 E2, we must make i = j.
So, answer is (C).
Question 23 |
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");
(A[i][j] && !A[j][i]) | |
(!A[i][j] && A[j][i]) | |
(!A[i][j] | | A[j][i]) | |
(A[i][j] | | !A[j][i]) |
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, E3 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 E3 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 |
- 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.

![]() | |
![]() | |
![]() | |
![]() |




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

>100 but finite | |
∞ | |
3 | |
>3 and ≤100 |
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 |
preorder traversal | |
in-order traversal
| |
depth first search
| |
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 |

(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 eWhich are depth first traversals of the above graph?
I, II and IV only | |
I and IV only | |
II, III and IV only | |
I, III and IV only
|
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 vi to vj in G is sequence of vertices (vi, vi+1, ......., vj) such that (vk, vk+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[j,k] ≤ n | |
If A[j,j] ≥ n - 1, then G has a Hamiltonian cycle
| |
If there exists a path from j to k, A[j,k] contains the longest path length from j to k | |
If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges
|

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?
{u, v} must be an edge in G, and u is a descendant of v in T | |
{u, v} must be an edge in G, and v is a descendant of u in T | |
If {u, v} is not an edge in G then u is a leaf in T | |
If {u, v} is not an edge in G then u and v must have the same parent in T |

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 |
0 | |
1 | |
2 | |
3 |
Total no. of articulation points = 3
Question 31 |
G has no cycles. | |
The graph obtained by removing any edge from G is not connected.
| |
G has at least one cycle. | |
The graph obtained by removing any two edges from G is not connected. | |
Both C and D. |
For example let us consider, n=3
Question 32 |
n-p |
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 |
d(r,u) | |
d(r,u)>d(r,v) | |
d(r,u)≤d(r,v) | |
None of the above |
Question 34 |
True | |
False |