Properties of Minimum Spanning Tree

What is a Spanning Tree?

A spanning tree is a subset of Graph G, such that all the vertices are connected using minimum possible number of edges. Hence, a spanning tree does not have cycles and a graph may have more than one spanning tree....

Properties of a Spanning Tree:

A Spanning tree does not exist for a disconnected graph.For a connected graph having N vertices then the number of edges in the spanning tree for that graph will be N-1.A Spanning tree does not have any cycle.We can construct a spanning tree for a complete graph by removing E-N+1 edges, where E is the number of Edges and N is the number of vertices.Cayley’s Formula: It states that the number of spanning trees in a complete graph with N vertices is For example: N=4, then maximum number of spanning tree possible = = 16 (shown in the above image)....

Real World Applications of A Spanning Tree:

Several path finding algorithms, such as Dijkstra’s algorithm and A* search algorithm, internally build a spanning tree as an intermediate step.Building Telecommunication Network.Image Segmentation to break an image into distinguishable components.Computer Network Routing Protocol...

Minimum Spanning Tree(MST):

The weight of a spanning tree is determined by the sum of weight of all the edge involved in it....

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....

Algorithms to Find Minimum Spanning Tree of a Graph:

There are several algorithms to find the minimum spanning tree from a given graph, some of them are listed below:...

1. Krushkal’s Minimum Spanning Tree:

Kruskal’s Minimum Spanning Tree (MST) algorithm is to connect all the vertices of a graph with the minimum total edge weight while avoiding cycles. This algorithm employs a greedy approach, meaning it makes locally optimal choices at each step to achieve a globally optimal solution....

2. Prim’s Minimum Spanning Tree:

Minimum Spanning Tree (MST) is to build the MST incrementally by starting with a single vertex and gradually extending the tree by adding the closest neighbouring vertex at each step....

3. Boruvka’s Algorithm:

This is also a graph traversal algorithm used to find the minimum spanning tree of a connected, undirected graph. This is one of the oldest algorithms. The algorithm works by iteratively building the minimum spanning tree, starting with each vertex in the graph as its own tree. In each iteration, the algorithm finds the cheapest edge that connects a tree to another tree, and adds that edge to the minimum spanning tree. This is almost similar to the Prim’s algorithm for finding the minimum spanning tree....

4. Reverse-Delete Algorithm:

Reverse Delete algorithm is closely related to Kruskal’s algorithm. In Kruskal’s algorithm what we do is : Sort edges by increasing order of their weights. After sorting, we one by one pick edges in increasing order. We include current picked edge if by including this in spanning tree not form any cycle until there are V-1 edges in spanning tree, where V = number of vertices. In Reverse Delete algorithm, we sort all edges in decreasing order of their weights. After sorting, we one by one pick edges in decreasing order. We include current picked edge if excluding current edge causes disconnection in current graph. The main idea is delete edge if its deletion does not lead to disconnection of graph....

Real World Application of A Minimum Spanning Tree:

Network design: Spanning trees can be used in network design to find the minimum number of connections required to connect all nodes. Minimum spanning trees, in particular, can help minimize the cost of the connections by selecting the cheapest edges.Image processing: Spanning trees can be used in image processing to identify regions of similar intensity or color, which can be useful for segmentation and classification tasks.Social network analysis: Spanning trees and minimum spanning trees can be used in social network analysis to identify important connections and relationships among individuals or groups....