Properties of Minimum Spanning Tree
- A minimum spanning tree connects all the vertices in the graph, ensuring that there is a path between any pair of nodes.
- An MST is acyclic, meaning it contains no cycles. This property ensures that it remains a tree and not a graph with loops.
- An MST with V vertices (where V is the number of vertices in the original graph) will have exactly V – 1 edges, where V is the number of vertices.
- An MST is optimal for minimizing the total edge weight, but it may not necessarily be unique.
- The cut property states that if you take any cut (a partition of the vertices into two sets) in the original graph and consider the minimum-weight edge that crosses the cut, that edge is part of the MST.
Minimum Spanning Tree of a Graph may not be Unique:
Like a spanning tree, there can also be many possible MSTs for a graph as shown in the below image:
Spanning Tree
In this article, we are going to cover one of the most commonly asked DSA topic which is the Spanning Tree with its definition, properties, and applications. Moreover, we will explore the Minimum Spanning Tree and various algorithms used to construct it. These algorithms have various pros and cons over each other depending on the use case of the problem.