Question 1 |
Let G(V, E) be a directed graph, where V = \{1, 2, 3, 4, 5 \} is the set of vertices and
E is the set of directed edges, as defined by the following adjacency matrix A.
A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.
A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____
A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.
A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____
24 | |
36 | |
12 | |
6 |
Question 1 Explanation:
Question 2 |
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
MSQ
MSQ
The edge with the second smallest weight is always part of any minimum spanning tree of G . | |
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . | |
Suppose S\subseteq V be such that S\neq \phi and S\neq V . Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G . | |
G can have multiple minimum spanning trees. |
Question 2 Explanation:
Question 3 |
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?
Both S1 and S2 are true | |
S1 is true and S2 is false | |
S1 is false and S2 is true | |
Both S1 and S2 are false |
Question 3 Explanation:
Question 4 |
Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is __________

The number of minimum-weight spanning trees of the graph is __________
4 | |
6 | |
5 | |
3 |
Question 4 Explanation:
Question 5 |
Consider a graph G=(V,E), where V=\{v_1,v_2,...,v_{100}\}, E=\{(v_i,v_j)|1\leq i \lt j\leq 100\}, and weight of the edge (v_i,v_j)\; is \; |i-j|. The weight of minimum spanning tree of G is _________
100 | |
99 | |
199 | |
90 |
Question 5 Explanation:
Question 6 |
Let G=(V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u,v)\in V \times V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
\Theta (|E|+|V|) | |
\Theta (|E||V|) | |
\Theta (|E|\log |V|) | |
\Theta (|V|) |
Question 6 Explanation:
Question 7 |
Let G be any connection, weighted, undirected graph:
I. G has a unique minimum spanning tree if no two edges of G have the same weight.
II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum weight edge crossing the cut.
Which of the above two statements is/are TRUE?
I. G has a unique minimum spanning tree if no two edges of G have the same weight.
II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum weight edge crossing the cut.
Which of the above two statements is/are TRUE?
I only | |
II only | |
Both I and II | |
Neither I nor II |
Question 7 Explanation:
Question 8 |
Consider the following undirected graph G:
Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.
3 | |
4 | |
5 | |
1 |
Question 8 Explanation:
Question 9 |
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only | |
(II) only | |
Both (I) and (II) | |
Neither (I) nor (II) |
Question 9 Explanation:
Question 10 |
G = (V,E) is an undirected simple graph in which each edge has a distinct weight,and e is a particular edgeof G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I only | |
II only | |
both I and II | |
neither I nor II |
Question 10 Explanation:
There are 10 questions to complete.
in ques 24 plz update option B (b-c) –> (d-c)
Thank You Amar,
We have updated the option.
Q 32 it should have been Emax with maximum weight instead of Emin.
Thank You Kushagra Dasila,
We have updated it.