Back to home

- What is Minimum Spanning Tree
- Properties Of Spanning Tree
- Mathematical Properties of Spanning Tree
- Application Of Spanning Tree

Logicmojo - Updated Sept 18, 2021

A spanning tree is a subset of an undirected Graph that has all the vertices connected by minimum number of edges. If all the vertices are connected in a graph, then there exists at least one spanning tree. In a graph, there may exist more than one spanning tree.

Properties

β’ A spanning tree does not have any cycle.

β’ Any vertex can be reached from any other vertex

**What is Minimum Spanning Tree?**

A Minimum Spanning Tree(MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To derive an MST, Primβs algorithm or Kruskalβs algorithm can be used.

We found three spanning trees off one complete graph. A complete undirected graph can have maximum **n ^{n-2}** number of spanning trees, where n is the number of nodes.
In the above addressed example, n is 3, hence

β’ It is a tree (i.e., it is acyclic).

β’ It covers all the vertices V β contains |V| β 1 edges.

β’ The total cost associated with tree edges is the minimum among all possible spanning trees.

β’ not necessarily unique.

We now understand that one graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph G β

β’ A connected graph G can have more than one spanning tree.

β’ All possible spanning trees of graph G, have the same number of edges and vertices.

β’ The spanning tree does not have any cycle (loops).

β’ Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.

β’ Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

**Mathematical Properties of Spanning Tree**

β’ Spanning tree has n-1 edges, where n is the number of nodes (vertices).

β’ From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

β’ A complete graph can have maximum n^{n - 2} number of spanning trees.

Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are β

β’ Civil Network Planning

β’ Computer Network Routing Protocol

β’ Cluster Analysis

The following algorithms are used to find the minimum spanning tree from a graph, which you can read about in the links below.

With this article at Logicmojo, you must have the complete idea of analyzing Minimum Spanning Tree

**Good Luck & Happy Learning!!**