Spanning Tree and Minimum Spanning Tree

Spanning Tree: In this tutorial, you will learn about spanning trees and minimum spanning trees with the assistance of examples and figures.

Before we learn about spanning trees, we need to understand two graphs: undirected graphs and directed graphs.

An undirected graph is a graph wherein the edges don’t point toward any path (ie. the edges are bidirectional).

• 

A connected graph is a graph wherein there is consistently a way from a vertex to some other vertex.

• 

What is a spanning tree?

The spanning trees of a graph (G) is a subset of G that covers the entirety of its vertices using the minimum number of edges.

A few properties of a spanning trees can be concluded from this definition:

1. Since “a spanning tree covers the entirety of the vertices”, it can’t be disconnected.
2. Spanning trees can’t have any cycles and comprise (n-1) edges (where n is the number of vertices of the graph) since “it uses the minimum number of edges”.

A graph can have more than one spanning tree. Truth be told, a total graph can have a maximum of n​ⁿ−^2​​  spanning trees.

• 

---

Spanning trees

A spanning trees is a sub-graph of an undirected associated graph, which incorporates all the vertices of the graph with a minimum conceivable number of edges. In the event that a vertex is missed, then it is not a spanning trees.

The edges could conceivably have weights assigned to them.

The total number of spanning trees with n vertices that can be created from a total graph is equivalent to n^(n-2)

On the off chance that we have n = 4, the maximum number of conceivable spanning trees is equivalent to 4^4-2 = 16. Along these lines, 16 spanning trees can be formed from a complete graph with 4 vertices.

---

Illustration of a Spanning Trees

Let’s understand the spanning trees with models underneath:

Let the original graph be:

• 

A portion of the conceivable spanning trees that can be created from the above graph is:

• 

• 

• 

• 

• 

• 

---

Minimum Spanning Trees

A minimum spanning trees is a spanning trees in which the sum of the weight of the edges is as minimum as possible.

---

Illustration of a Spanning Trees

Let’s understand the above definition with the assistance of the example underneath.

The underlying diagram is:

• 

The possible spanning trees from the above graph are:

• 

• 

• 

• 

The minimum spanning trees from the above spanning trees is:

• 

The minimum spanning trees from a graph is found using the following algorithms:

---

Spanning Trees Applications

• Computer Network Routing Protocol
• Cluster Analysis
• Civil Network Planning

---

Minimum Spanning trees Applications

• To find paths in the map
• To design networks like telecommunication networks, water supply networks, and electrical grids.

---

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.

Graph-based DSA