Spanning Tree | Minimum Spanning Tree — [Notes]

Spanning Tree

A spanning tree is a sub-graph of an undirected connected graph, which

1. should contain no cycle
2. should include all the vertices of the graph
3. should contain (|V|-1) edges
4. all edges should be connected

• If a vertex is missed, then it is not a spanning tree.
• The edges may or may not have weights assigned to them.

The total number of spanning trees with n vertices that can be created from a complete graph is equal to n^(n-2)

n= 3, spanning trees = n^(n-2) |3¹ = 3

Minimum Spanning Tree

• A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.

https://whimsical.com/spanning-tree-YYgvKTW5hUBmWZmux4zGW7

Algorithms —

The minimum spanning tree from a graph is found using the following algorithms:

1. Prim’s Algorithm
2. Kruskal’s Algorithm

Spanning Tree Applications

• Computer Network Routing Protocol
• Cluster Analysis
• Civil Network Planning

Minimum Spanning tree Applications

• To find paths in the map
• To design networks like telecommunication networks, water supply networks, and electrical grids.