Spanning Trees

Question 1

What is the invariant in the algorithm?

Answer 1

Prior to each iteration, A is a subset of some mininum spanning tree.

Question 2

Prove the theorem

Answer 2

Question 3

disjoint-set-forest

For a sequence of:

• O(|V|) - MAKE-SET operations
• at most O(|V|) - UNION operations
• 2|E|-1 = O(|E|) - FIND-SET operations

what is the run-time of all this operations?

Answer 3

Run-Time:

O(|E|log(|E|)) = O(|E|log|V^2|)=O(|E|log(|V|))

Question 4

Prove the corollary

Answer 4

Question 5

Kruskal algorithm

Answer 5

Question 6

Prim’s algorithm

Answer 6

Question 7

What is a bottleneck spanning tree?

Answer 7