Minimum Spanning Tree(MST)
- Let G = (V, E) be a simple, connected, undirected graph that is not edge-weighted.
- A spanning tree of G is a free tree (i.e., a tree with no root) with | V | - 1 edges that connects all the vertices of the graph.
- Thus a minimum spanning tree for G is a graph, T = (V’, E’) with the following properties:
V’ = V
T is connected
T is acyclic.
- A spanning tree is called a tree because every acyclic undirected graph can be viewed as a general, unordered tree. Because the edges are undirected, any vertex may be chosen to serve as the root of the tree.