Minimum Spanning Tree: Difference between revisions

From Rice Wiki
VisualWikitext
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]].
== 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 <math>T</math> vs. <math>V - T</math>
Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.
<math>
OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
</math>


= 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 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.

Suboptimality

The MST problem exhibits the optimal substructure property.

Given MST tree for the graph G

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 OPT = \text{set of edges} }

where the number of edges is 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 n - 1} , the weight of edges is minimum, and the tree is spanning.

Consider 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 (x,y)} , where X is a leaf node.

Prove that is a MST for the subproblem 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 - X}

By contradiction, assume that 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} is not optimal. There must be 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} such that

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(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.

Retrieved from "http://ricefriedegg.com:80/mediawiki/index.php?title=Minimum_Spanning_Tree&oldid=412"