Minimum Spanning Tree

Question 1

Define a spanning tree

Answer 1

A spanning tree is an acyclic subset of edges that connects all nodes in a graph.

Question 2

Define a minimum spanning tree

Answer 2

A spanning tree with the minimum weight.

Question 3

Proof that a minimum spanning tree is acyclic.

Answer 3

If an MST is cyclic, that means there is an edge which we can remove to make the MST lighter. Thus, this proves the contradiction that the original cyclic spanning tree is an MST.

Question 4

Is MST and shortest path the same? Explain.

Answer 4

MST and shortest path are not the same. An MST gives you a tree which traverse through all the nodes with the least weight. Shortest path does not need to traverse through all the nodes, it just gives the shortest path between two given nodes in the graph.

Question 5

Basic properties of an MST.

Answer 5

1. No cycles
2. Cutting an MST produces two separate MSTs
3. Cycle property: for every cycle, the maximum weight edge is NOT in the MST.
4. Cut property: for every partition of the nodes, the minimum weight edge across the cut IS in the MST.
5. For every vertex, the minimum outgoing edge is in the MST.

Question 6

Explain the generic MST algorithm.

Answer 6

Red rule: if C is a cycle with no red arcs, color the max weight edge in C red.
Blue rule: if D is a cut with no blue arcs, color the min weight edge in D blue.
On termination, all edges will be colored either red or blue. All the blue edges will be our MST (otherwise there is a cut with no blue edge) and all cycles will have a red edge (there can not be a blue cycle).

Question 7

Explain Prim’s algorithm.

Answer 7

1. Start with a root node. Call this node R.
2. Look at all the edges going out from this node, take the minimum one. Store the rest in a priority queue. These edges are the edges that crosses the cut which separates our R from the rest of the graph.
3. The minimum edge connects R to another node, call this A. Now recurse the whole process in step 2 where the edges now are the edges that crosses the cut which separates our R and A from the rest of the graph.
4. Recurse until we have covered all nodes. The edges we obtain forms our desired MST.

Question 8

Why is Prim’s algorithm called the “blue” algorithm?

Answer 8

It’s because the basic idea stems from the blue rule, in which all the edges added during the recursion are each the lightest edge on some cut in the graph.

Question 9

Explain Kruskal’s algorithm.

Answer 9

1. Sort all the edges by their weight.
2. From lightest to heaviest, check each edge and see if it connects two nodes which are a part of the same connected component (blue tree). If yes, color this edge red. If no, color this edge blue.
   We also use Union-Find to find the nodes and check if they are in the same connected component and to merge two connected components.

Question 10

Analyse the running time of Prim’s algorithm.

Answer 10

Constructing the priority queue takes O(VlogV) for V nodes. We will perform the decreaseKey at most E times which takes O(ElogV). Total: O(VlogV) + O(ElogV) and since E = O(V^2), the total is O(ElogV).

Question 11

Analyse the running time of Kruskal’s algorithm.

Answer 11

Sorting all the edges by their weight will take O(ElogE) time. For each edge, using Union-Find will take O(α(V)).
Total: O(ElogE) + O(Eα(V)) and since E = O(V^2) and O(Eα(V)) is basically O(E), we can also rewrite this as O(ElogV).

Question 12

Explain Boruvka’s algorithm.

Answer 12

One Boruvka’s step does:

1. For each connected component. search for the minimum weight outgoing edge. This can be done using BFS or DFS which takes O(V + E).
2. Add these selected edges.
3. Merge the components which are connected by these edges.

Question 13

Analyse the running time of Boruvka’s algorithm.

Answer 13

At most we have to perform logV Boruvka steps. This only happens when each merge only connected component to another. Thus, the worst case runtime is O((V+E)logV) = O(ElogV). But most of the time it will run much faster than this.

Question 14

What if all the edges have the same weights?

Answer 14

We can just perform a DFS or BFS to find the shortest path which will also be our MST.

Question 15

If the edges are all of cost X, what is the cost of the MST?

Answer 15

(V-1)X

Question 16

What if all the edges have weights ranging from {1…10}?Solve using Kruskal’s algorithm.

Answer 16

1. Use an array of size 10 where each slot holds a linked list.
2. Put the edges in the corresponding linked list (by weight of the edge).
3. Iterate over all the edges in ascending order. For each edge, using Union-Find allows us to find and union in O(α(V)).
   Total runtime: O(Eα(V)).

Question 17

What if all the edges have weights ranging from {1…10}? Solve using Prim’s algorithm.

Answer 17

1. Use an array of size 10 where each slot holds a linked list. This acts as our priority queue.
2. Put the nodes in the corresponding linked list (by priority of the node).
   It takes O(V) to build the array and inserting or deleting from the array. It takes O(E) to decreaseKey.
   Total runtime: O(V + E).

Question 18

How do we find the MST for a directed acyclic graph with one root?

Answer 18

1. Start at a root with no incoming edge to it.
2. For every node except the root, add the minimum weight incoming edge to that node.
3. The edges will form our MST.

Question 19

Does adding a constant k to all the weights of the edges matter?

Answer 19

Nope! Only relative weights matter.

Question 20

Are negative edge weights allowed in our MST algorithm?

Answer 20

Yup! Negative edge weights does not provide any problems.

Question 21

How do we find the Maximum Spanning Tree?

Answer 21

We can multiply all the edges’ weights by -1 and perform our MST on the new graph. The MST we obtain in this new graph is the Maximum Spanning Tree of our original graph.

Question 22

Explain the Steiner Tree problem and the problems we face when trying to solve it. Provide the algorithm which gives us a close estimate to the actual MST.

Answer 22

The Steiner Tree problem is when we would like to find the MST of only some of the nodes in a given graph. Some problems we face when trying to solve this is:
1. We can try to get the MST of just the required nodes in the graph. However, there may be a lighter MST which involves traversing through some Steiner nodes.
2. We can try to get the MST of all the nodes in the graph. However, there may be a lighter MST which doesn’t involve traversing through all the Steiner nodes.
SteinerMST algorithm:
1. For every pair of required vertices (v, w), calculate the shortest path between them using Dijkstra’s algorithm.
2. Construct a new graph of the required nodes where the edges connecting the required nodes are the shortest paths between them which was obtained in step 1.
3. Run MST on this new graph.
4. Map back the new edges to the original graph.