Latest revision as of 17:40, 20 March 2024

A minimum spanning tree is

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

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

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.

@@ Line 1: / Line 1: @@
-[[Category:Algorithms]]
-= Description =
 A '''minimum spanning tree''' is
 * a tree, meaning it has no cycle
@@ Line 8: / Line 4: @@
 * spanning, meaning it connects all nodes
-The input is an undirected, weighted graph <math>G</math>. The output is
+The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph.
-a tree that
+Algorithm that solves this problem includes [[Kruskal's Algorithm]] and [[Prims Algorithm]].
-* connects all vertices
+= Suboptimality =
-* has minimum weight
+The MST problem exhibits the optimal substructure property.
+Given MST tree for the graph G
+<math>
+OPT = \text{set of edges}
+</math>
+where the number of edges is <math>n - 1</math>, the weight of edges is
+minimum, and the tree is spanning.
+Consider <math>(x,y)</math>, where X is a leaf node.
+Prove that <math>A = OPT - (x, y)</math> is a MST for the subproblem
+<math>G - X</math>
+By contradiction, assume that <math>A</math> is not optimal. There must
+be <math>B</math> such that
+<math>
+w(B) < w(A)
+</math>
+Adding the edge (x, y) back to both graphs
+<math>B + (x, y)</math> is a viable tree.
+<math>
+ w(B + w(x,y)) < w(A + w(x,y)) = w(OPT)
+</math>
+Therefore, OPT is not the optimal solution.
+By contradiction, <math>A</math> must be optimal.
+[[Category:Algorithms]]