Sunday, 13 June 2021

Spanning Tree and minimum spanning tree in graphs

 What is spanning Tree?

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices

We found three spanning trees off one complete graph. A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 33−2 = 3 spanning trees are possible.

Properties of Spanning Tree

  1. Spanning tree has n-1 edges, where n is the number of nodes (vertices).
  2. From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.
  3. A complete graph can have maximum nn-2 number of spanning trees.

Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

Minimum Spanning Tree (MST)

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

Minimum Spanning-Tree Algorithm

We shall learn about two most important spanning tree algorithms here −

  1. Prim's algorithm 
  2. Krushkal's algorithm 

Both are greedy algorithms.


Post a Comment

Note: only a member of this blog may post a comment.

Find Us On Facebook

python tutorial


C Programming


Java Tutorial


Data Structures


MS Office


Database Management