Minimum Spanning Tree

A minimum spanning tree is

• a tree, meaning it has no cycle
• minimum, meaning it has minimum weight
• spanning, meaning it connects all nodes

MST Problem

The MST problem takes a connected graph $G$ and outputs an MST for that graph.

Approach: Greedy

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of $T$ vs. $V-T$

Given the MST of $V_{n-m}=v_{1},v_{2},\ldots ,v_{n-m}$, the MST of $V$ should be that of $V_{n-1}$ plus the edge that connects to $v_{n}$ that is the shortest.

$OPT(n)=OPT(n-1)+min((v_{i},v_{n})\in E)$

Suboptimality

The MST problem exhibits the optimal substructure property.

Given MST tree for the graph G

$OPT={\text{set of edges}}$

where the number of edges is $n-1$, the weight of edges is minimum, and the tree is spanning.

Consider $(x,y)$, where X is a leaf node.

Prove that $A=OPT-(x,y)$ is a MST for the subproblem $G-X$

By contradiction, assume that $A$ is not optimal. There must be $B$ such that

$w(B)<w(A)$

Adding the edge (x, y) back to both graphs

$B+(x,y)$ is a viable tree.

$w(B+w(x,y))<w(A+w(x,y))=w(OPT)$

Therefore, OPT is not the optimal solution.

By contradiction, $A$ must be optimal.