Week 6 - Minimum Spanning Tree

Statement

Minimum Spanning Tree problem

Given an undirected graph with weights can you find a spanning tree with minimum weight

Link to original

Tree properties

It is useful to remind ourselves of some tree properties:

1. Tree on vertices has edges.
2. In a tree, there is exactly one path between every pair of vertices.
3. Any connected with is a tree.

These are all proved by the equivalent tree definitions.

Greed is good … in this case

The greedy approach of just starting with an empty graph and keep adding valid edges of minimum weight, solves the MST problem.

The only problem is keeping track of the edges that are valid to include.

Kruskal’s Algorithm

Pseudocode

Kruskal's(G,w):
	Input: undirected graph G=(V,E) with weights w(e).
	Output: MST edges X
1. Sort E by weights, smallest to largest
2. Set X to be empty
3. For e = (v,w) in E (ordered)
	1. If X U e does't have a cycle then X = X U e.
4. Output X

Link to original

Run time

For step 1, we use merge sort so this takes time. Though as , we can think of this as .

Step 3, has steps in each one we run two operations in the union-find data structure both of which take time. So this is .

So in total this takes .

Link to original

Correctness

We prove by induction on the size of that this must be a subset of some MST.

Base case

.

Note there must be an MST and . Therefore and we have shown it true for the base case.

Induction case

Suppose for some MST .

Suppose we want to add some edge . Let be the connected component of containing . Note as contains no cycles.

This forms cut with . is of minimum weight otherwise we would have added that edge already.

Therefore by the cut property is contained in some MST .

This proves the induction case and we have that is always a subset of some MST.

Conclusion

As the algorithm considers adding every edge and adds it if and only if it doesn’t add cycle the output is a spanning tree. This is also minimal as is always a subset of an MST giving the algorithm is correct.

Link to original

So the only think left to prove Kruskal’s algorithm is correct is the proof of the cut property.

Cut property

Cut property

Let be an undirected graph with an edge weight . Suppose is part of an MST . Let be a cut where no edge of is in the cut edges . Then for of minimum weight - is part of an MST .

Proof

If then and we are done.

Assume .

Let . As is an MST it contains a path from to . As and the path contains an edge .

Let .

We have the size of is as is a tree.

Consider the cycle - rewrite this cycle as . We will use this to show is connected.

Let . As is connected there must a path in connecting to .

If uses replace by to form which only uses edges in . As connects to we have is connected.

As is connected on and has edges it has to be a spanning tree of .

Note as is the minimum weight edge in we have and moreover This gives that is of minimum weight as was a MST.

All together this gives us that is an MST where , proving the statement.

Link to original

Prim’s algorithm

Algorithm

Prim's(G,w):
	Input: undirected graph G=(V,E) with weights w(e).
	Output: MST defined by the array prev
for all u in V
	cost(u) = inf
	prev(u) = nil
Pick any initial node u_0
cost(u_0) = 0
 
H = makequeue(V)
while H is not empty:
	v = deletemin(H)
	for each {v,z} in E:
		if cost(z) > w(v,z):
			cost(z) = w(v,z)
			prev(z) = v
			decreasekey(H,z)
output prev

Link to original

Correctness

Note that functionally Prim’s algorithm is slowly building a tree using the closes vertex to the currently constructed tree that is not already in it.

We prove by induction on the size of that this must be a subset of some MST.

Base case

.

Note there must be an MST and . Therefore and we have shown it true for the base case.

Induction case

Suppose for some MST .

Suppose we find the next closest vertex . I.e. There is some minimum weight edge the cut edges of .

Therefore by the cut property is contained in some MST .

This proves the induction case and we have that is always a subset of some MST.

Conclusion

As the algorithm runs until each vertex is added to the tree . is a spanning tree which is a subset of a MST. Therefore is an MST in its own right.

Link to original