Spanning tree and Minimum Spanning tree with example

What is Spanning Tree?

A spanning tree of a graph G is a special subgraph that includes all the vertices of the graph but only enough edges to form a tree. This means it connects every vertex without forming any cycles. A spanning tree always has the minimum number of edges required to keep all vertices connected. Every connected and undirected graph has at least one spanning tree, and sometimes it can have multiple spanning trees. Spanning trees are useful in applications like network design, where we want to connect all points efficiently without creating loops.

Example of spanning tree

Suppose we have a graph containing V vertices and E edges. We can denote it as G(V,E)

Below is a undirected connected graph

The spanning tree must contain all the vertices of the graph, but it will always have exactly one less edge than the total number of vertices, meaning if a graph has V vertices, its spanning tree will have V – 1 edges.

The spanning tree of a graph G(V, E) is represented as:
G(V, E′)

where,
V′ = V
E′ = |V| – 1, with E′ ⊆ E

Lets understand with the help of below example

Here we are going to create spanning tree of the below graph

Properties of Spanning Tree

From the above example, We understand that a graph can have more than one spanning tree. Below are a few properties of the spanning tree −

• A connected graph G can have more than one spanning tree.
• All possible spanning trees of the graph has the same number of vertices and edges.
• Spanning tree does not contain any loops/cycles.
• If we remove any one edge from the spanning tree, the graph becomes disconnected.
• If we add anyone edge to the spanning tree, it will create a circuit or loop in the graph. So we can say that the spanning tree is maximally acyclic.
• For n vertices, A Spanning tree has n-1 edges.
• A complete graph can have a maximum n^n-2 number of spanning trees.

Minimum Spanning Trees

The minimum spanning tree (MST) of a connected, weighted, undirected graph is a spanning tree in which the total sum of the edge weights is the smallest possible among all spanning trees of that graph. In simple words, it connects all the vertices together with the least total cost, without forming any cycles. The MST is widely used in real-life applications like designing efficient road networks, electrical circuits, communication links, and many other situations where we want to connect all points in the cheapest way.

Example of Minimum Spanning Trees

Here we are going to find minimum spanning tree for the below graph. There are more than one spanning tree can be formed using below graph but only one will be minimum spanning tree.

We have created 4 spanning trees from the above-weighted graph. But their sum of weight will be different. Below all the 4 spanning graph has a different sum of weight 15, 17, 14, 20. But the spanning tree that has a minimum sum of edges will be a minimum spanning tree. Here 14 is the minimum so the tree with edge sum of 14 will be the minimum spanning tree.

Minimum spanning tree

Minimum Spanning-Tree Algorithm

The two most important Minimum Spanning-Tree Algorithm are

• Kruskal’s Algorithm
• Prim’s Algorithm

Both are greedy Algorithms

Application of Minimum Spanning Tree

• Cluster Analysis
• Handwriting recognition
• Image segmentation
• Civil Network Planning
• Computer Network Routing

Application of MST in detail

Minimum Spanning Tree (MST) is widely used in designing efficient networks. For example, consider a telephone network connecting people who live far apart. An MST helps find the cheapest way to connect everyone without creating any loops or cycles.

Similarly, MSTs can be used to design airline routes. Here, cities are represented as vertices, and routes between cities are represented as edges. Using an MST, we can determine the least costly routes that connect all cities without repeating any paths or forming cycles. This helps save cost while ensuring every location is reachable.

Difference Between Spanning tree and Minimum Spanning tree

spanning tree vs minimum spanning tree

Conclusion

 Spanning tree is a simplified form of a graph that connects all the vertices using the minimum number of edges without forming any cycles. It always has V – 1 edges for V vertices and ensures that the graph remains connected in the simplest way. Spanning trees, and especially minimum spanning trees, are very useful in real-life applications where efficient and cost-effective connections are required, such as in network design, transportation, and communication systems.