1. Intro to MST #
Created Sunday 19 April 2020
Minimum Spanning Tree #
Tree: A connected graph with no cycles.
Spanning Tree: Given a simple(no loops or multiedge) undirected connected graph, a tree containing all the vertices of the graph is called a spanning tree.
- There can be multiple MSTs for a given graph.
- For a spanning tree: |N|-|E| = 1
**Minimum Spanning Tree: **For a weighted, connected and undirected graph, a minimum spanning tree(MST) is a tree with the least weight. **There could be multiple MST’s for the same graph. **
Remember the MST requirements for a given graph:
- Weighted
- Undirected
- Connected
Multiplicity of MST’s for a given graph: Experimentation shows that multiple trees can exist. Remember tree signatures are different. i.e Graph matrices should be different. Uniqueness: If each edge has a distinct weight then there will be only one, unique minimum spanning tree. **Simple proof. **For different trees, at least one edge is different. If two MST’s were possible, then we need to have
Invariants and Properties:
- Adding any edge to an MST creates a cycle.
Finding MST for a given weighted, connected and undirected graph.
Naive Approach:
- Find all the Spanning trees.
- Find weight of each(i.e sum of edges)
- Trees with minium values of weight are MSTs.