Minimum Spanning Tree: Difference between revisions
From Rice Wiki
No edit summary |
|||
Line 7: | Line 7: | ||
Algorithm that solves this problem includes [[Kruskal's Algorithm]] and [[Prims Algorithm]]. | Algorithm that solves this problem includes [[Kruskal's Algorithm]] and [[Prims Algorithm]]. | ||
= Suboptimality = | = Suboptimality = |
Latest revision as of 17:40, 20 March 2024
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 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
where the number of edges is , the weight of edges is minimum, and the tree is spanning.
Consider , where X is a leaf node.
Prove that is a MST for the subproblem
By contradiction, assume that is not optimal. There must be such that
Adding the edge (x, y) back to both graphs
is a viable tree.
Therefore, OPT is not the optimal solution.
By contradiction, must be optimal.