Minimum Spanning Tree - Revision history

Rice: /* Approach: Greedy */

2024-03-20T17:40:48Z

Approach: Greedy

← Older revision		Revision as of 17:40, 20 March 2024
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 =

2024-03-12T23:49:01Z

← Older revision		Revision as of 23:49, 12 March 2024
Line 4:		Line 4:
	* spanning, meaning it connects all nodes		* spanning, meaning it connects all nodes

	= MST ~~Problem =~~		The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph.

	~~The '''MST~~ problem'~~'' takes a connected graph <math>G</math>~~ and ~~outputs an MST for that graph~~.		Algorithm that solves this problem includes [[Kruskal's Algorithm]] and [[Prims Algorithm]].

	== Approach: Greedy ==		== Approach: Greedy ==

2024-03-08T01:27:19Z

Implementation

← Older revision		Revision as of 01:27, 8 March 2024
Line 18:		Line 18:
	</math>		</math>

			= Suboptimality =

			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.

	~~== Implementation ==~~

	~~<pre>~~
	~~MST(G):~~
	~~mst_nodes = start_node~~
	~~mst = adjacency list with no edges~~
	~~# candidate_edges is a min heap~~
	~~candidate_edges = (start_node, G[start_node])~~
	~~while mst_nodes is not spanning:~~
	~~new_edge = candidate_edges.pop()~~
	~~</pre>~~

	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-06T01:57:10Z

← Older revision		Revision as of 01:57, 6 March 2024
Line 6:		Line 6:
	= MST Problem =		= MST Problem =

	The '''MST problem''' takes a connected graph <math>G</math> and outputs		The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph.
	an MST for that graph.

	== Approach: Greedy ==		== Approach: Greedy ==

	The approach is to try to add the smallest edges as long as they do not		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>
	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 - 1} = v_1, v_2, \ldots, v_{n-1} </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.
	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>		<math>

2024-03-06T01:37:58Z

← Older revision		Revision as of 01:37, 6 March 2024
Line 23:		Line 23:
	</math>		</math>


			== Implementation ==

			<pre>
			MST(G):
			mst_nodes = start_node
			mst = adjacency list with no edges
			# candidate_edges is a min heap
			candidate_edges = (start_node, G[start_node])
			while mst_nodes is not spanning:
			new_edge = candidate_edges.pop()
			</pre>

	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-06T01:24:19Z

← Older revision		Revision as of 01:24, 6 March 2024
Line 15:		Line 15:
	of <math>T</math> vs. <math>V - T</math>		of <math>T</math> vs. <math>V - T</math>

	Given the MST of <math>V_{n - 1} </math>, the MST of <math>V</math>		Given the MST of <math>V_{n - 1} = v_1, v_2, \ldots, v_{n-1} </math>,
	should be that of <math>V_{n-1}</math> plus the edge that connects to		the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus
	<math>v_n</math> that is the shortest.		the edge that connects to <math>v_n</math> that is the shortest.

	<math>		<math>

2024-03-06T01:21:49Z

Approach: Greedy

← Older revision		Revision as of 01:21, 6 March 2024
Line 15:		Line 15:
	of <math>T</math> vs. <math>V - T</math>		of <math>T</math> vs. <math>V - T</math>

	Given the MST of <math>V_{n - 1}</math>, the MST of <math>V</math>		Given the MST of <math>V_{n - 1} </math>, the MST of <math>V</math>
	should be that of <math>V_{n-1}</math> plus the edge that connects to		should be that of <math>V_{n-1}</math> plus the edge that connects to
	<math>v_n</math> that is the shortest.		<math>v_n</math> that is the shortest.

2024-03-06T01:21:16Z

← Older revision		Revision as of 01:21, 6 March 2024
Line 9:		Line 9:
	an MST for that graph.		an MST for that graph.

	== Greedy ~~Approach~~ ==		== Approach: Greedy ==

	The approach is to try to add the smallest edges as long as they do not		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		create a cycle; add an edge to the tree that is minimum across the cut
	of <math>T</math> vs. <math>V - T</math>		of <math>T</math> vs. <math>V - T</math>

			Given the MST of <math>V_{n - 1}</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>


	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-06T01:13:06Z

← Older revision		Revision as of 01:13, 6 March 2024
Line 4:		Line 4:
	* spanning, meaning it connects all nodes		* spanning, meaning it connects all nodes

			= MST Problem =

			The '''MST problem''' takes a connected graph <math>G</math> and outputs
			an MST for that graph.

			== Greedy Approach ==

			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>


	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-06T00:56:07Z

← Older revision		Revision as of 00:56, 6 March 2024
Line 1:		Line 1:
	~~= Description =~~

	A '''minimum spanning tree''' is		A '''minimum spanning tree''' is
	* a tree, meaning it has no cycle		* a tree, meaning it has no cycle
	* minimum, meaning it has minimum weight		* minimum, meaning it has minimum weight
	* spanning, meaning it connects all nodes		* spanning, meaning it connects all nodes



	[[Category:Algorithms]]		[[Category:Algorithms]]