Lab: Minimum Spanning Trees

Algorithms

There are 2 main Minimum Spanning Tree algorithms we will consider.

1. Prim’s Algorithm which you read about in the reading. This effectively works by finding the next closest vertex to add to the graph.
2. Kruskal’s Algorithm. This works by adding the cheapest edge in the graph that connects 2 unconnected vertices.

Note: For this class, break ties alphabetically and start with vertex A when you have a choice of vertices to add/connect.

Problem 1: Using the algorithms

Consider the following weighted, undirected graph:

1. Come up with at least three spanning trees for this graph using the techniques discussed in the reading. Write down the collection of edges that compromises each tree. (Or draw the tree)
2. When our graphs have weights, we are concerned with finding minimum spanning trees (MSTs), spanning trees whose sum-of-weights-of-edges is minimal for any spanning tree of the graph. 2a. Use Prim’s algorithm as described in the reading to come up with a MST for this graph. 2b. Use Kruskal’s algorithm as described in the link to come up with a MST for this graph.

Note the edges of your MST and the sum-of-weights of that tree. Check with an instructor that your MST is indeed the minimal one.

1. Are the two MST the same? Why or why not?

Problem 2: Theory behind the algorithms

1. If the weights of the edges in a graph are unique, is the MST always unique?
2. If the weights of the edges in a graph aren’t unique, can the MST be unique?
3. Does Prim’s Algorithm work with negative weight edges? Why or why not?
4. Does Kruskal’s Algorithm work with negative weight edges? Why or why not?

Bonus: More difficult proofs

1. Given a weighted graph, G, and associated MST M. If we increase or decrease the weights of G by the same value, b, is M still an MST of G?
2. Given a weighted graph, G, and associated MST M. If we multiply the weights of G by the same value, c, is M still an MST of G? 2a. If you find a number such that this isn’t true, what if c can’t be that number? 2b. If you find that the sign on c matters, why?

Note: you may find this graph useful when thinking about Problems 2 and 3: