Minimum Spanning Trees

MINIMUM SPANNING TREES:

·        A Spanning tree of an undirected graph, G is a tree formed from graph edges that connects all vertices of G.

·        A Minimum Spanning tree of an undirected graph, G is a tree formed from graph edges that connects all vertices of G at lowest cost.

·        A minimum spanning tree exists if and only if G is connected. The number of edges in the minimum spanning tree is |V| -1.

·        The minimum spanning tree is a tree because it is acyclic, it is spanning because it covers every vertex, and it is minimum because it covers with minimum cost.

·        The minimum spanning tree can be created using two algorithms, that is prim’s algorithm and kruskal’s algorithm.