25.5 MST Exercises

Factual

1. Select all valid MSTs in the diagram below.

2. True/False: It is possible that the only Shortest Path Tree is the only Minimum Spanning Tree.

Problem 1

Only B. C and D have cycles; A does not span all vertices.

Problem 2

True. In a tree, there is only one SPT and MST.

Procedural

1. Run Prim's from A in the graph below. In what order are vertices visited? Break ties alphabetically.

2. Run Kruskal's in the graph below. In what order are edges added to the tree? Break ties alphabetically.

3. Design an algorithm to find the min-product spanning tree; ie the spanning tree with the minimum product of its edges. You may assume all edge weights are > 1.

Problem 1

Order: A B D C F G E. Prim's repeatedly picks the lightest edge between the current tree and any node not in the tree.

Problem 2

AB, BD, CF, FG, AC, EG. Kruskal's keeps adding the next lightest edge as long as it doesn't form a cycle.

Problem 3

Simply take the logarithm of each edge weight, then run any MST algorithm on it. This is guaranteed to work since $\log a + \log b = \log ab$, and minimizing the logarithm of the product is the same as minimizing the product for positive weight edges.

Metacognitive

1. If we add 1 to the weight of each edge in an arbitrary graph, will the MST created by Kruskal’s change?

2. True/False: Prim’s Algorithm and Kruskal’s algorithm will always return the same result. If this is true, explain why. If this is false, provide a counterexample, breaking ties alphabetically.

3. Prove the following, known as the cycle property: Given any cycle in an edge weighted graph (all edge weights distinct), the edge of maximum weight in the cycle does not belong to the MST of the graph.

Problem 1

Adding 1 to each number will not change the order of the edges when we sort them, therefore we will get the same MST.

Problem 2

False. A counterexample is the following graph:

Prim’s starting from A will select AD, BD, and CD, whereas Kruskals will select AD, BC, and BD.

Problem 3

Suppose, for contradiction, the maximum-weight edge f in a cycle is present in the MST.

Removing f disconnects our MST T. Form a cut with the two sides of the MST after f is removed.

Since f is part of a cycle, there must be also some edge e crossing that same cut. However, if we replace f with e, we now have a spanning tree that has less weight than our MST T.

This is a contradiction, so the maximum weight edge in a cycle cannot be part of the MST.