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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.