 # Introduction to Minimum Spanning Tree (MST)

What is a Spanning Tree?

In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph may have several spanning trees. The cost of the spanning tree is the sum of the weights of all the edges in the tree

What is a Minimum Spanning Tree?

minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. Number of edges in MST: V-1 (V – no of vertices in Graph).

Example: Algorithms for finding the Minimum Spanning Tree:

Applications:

Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids. Also used in

• Approximating travelling salesman problem
• Approximating multi-terminal minimum cut problem
• Approximating minimum-cost weighted perfect Cluster Analysis
• Handwriting recognition
• Image segmentation
• Circuit design

Reference – wiki

This site uses Akismet to reduce spam. Learn how your comment data is processed.