# Minimum Spanning Tree

 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 24 B 36 C 12 D 6
GATE CSE 2022   Algorithm
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
 A The edge with the second smallest weight is always part of any minimum spanning tree of G . B One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . C 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 . D G can have multiple minimum spanning trees.
GATE CSE 2022   Algorithm
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?
 A Both S1 and S2 are true B S1 is true and S2 is false C S1 is false and S2 is true D Both S1 and S2 are false
GATE CSE 2021 SET-2   Algorithm
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 __________
 A 4 B 6 C 5 D 3
GATE CSE 2021 SET-1   Algorithm
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 _________
 A 100 B 99 C 199 D 90
GATE CSE 2020   Algorithm
Question 5 Explanation:

There are 5 questions to complete.

### 8 thoughts on “Minimum Spanning Tree”

1. in ques 24 plz update option B (b-c) –> (d-c)

• Thank You Amar,
We have updated the option.

2. Q 32 it should have been Emax with maximum weight instead of Emin.

• Thank You Kushagra Dasila,
We have updated it.

3. In Question 26, please update option C to (d-f),(a-b),(d-c),(b-f),(d-e)

• Option updated for GATE CSE

4. • 