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

The MST problem takes a connected graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and outputs an MST for that graph.

Algorithm that solves this problem includes Kruskal's Algorithm and Prims Algorithm.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} vs. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B + (x, y)} is a viable tree.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(B + w(x,y)) < w(A + w(x,y)) = w(OPT) }

Therefore, OPT is not the optimal solution.

By contradiction, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} must be optimal.