The cheapest way to connect everything

Computing · Algorithms & Data Structures · ages 20-21

Name ______________________ Date ____________

Kruskal runs on a connected graph with 6 vertices. How many edges does the finished tree hold?
Answer: ______________
A connected graph has 6 vertices and 8 edges. A spanning tree is made by deleting edges until no loops remain while keeping the graph connected. How many edges does the spanning tree keep?
- 5
- 6
- 7
- 8
Kruskal's method is run on a connected graph with 6 vertices. When the method stops, how many edges does the built tree have?
Answer: ______________
On vertices A, B, C, D with weights AB 1, CD 2, AC 3, BC 4, BD 5, why is BC rejected?
- Adding BC would create a loop A to B to C to A
- BC is the heaviest edge in the graph
- B and C sit in separate pieces, so BC cannot be used
A connected graph holds 7 vertices and 9 edges. A spanning tree is cut down to no loops. How many edges were deleted?
Answer: ______________
A cut splits the vertices into two groups and E is the lightest edge crossing it. Why is E safe?
- E is automatically the lightest edge in the whole graph
- Adding E can never create a loop whatever exists already
- Some minimum spanning tree must include E, so adding it can never hurt
In a union-find forest, calling find(E) walks up the chain E to D to B to A, where A is the root. What does path compression change during this call?
- It points D and E straight at A, so later finds on this chain are shorter
- It sorts the forest by height so A is no longer the root
- It deletes the edge from B to A and splits the set
- It rebuilds the whole forest from scratch
Find on E walks up E to D to B to root A. What does path compression change?
- It sorts the forest by height so A is no longer the root
- It points D and E straight at A, so later finds on this chain are shorter
- It deletes the link from B to A and splits the set
Kruskal examines an edge whose ends already share a root in the union find forest. What must it do, and why?
- Add it anyway, since more edges always lower the total weight
- Skip it, since its ends are already connected and it would close a loop
- Stop the whole method, since shared roots mean the graph is broken
A student unions two trees but skips path compression ever after, claiming finds stay just as fast. What is wrong?
- Nothing is wrong, since compression never changes any speed
- Skipping it breaks the tree into separate graphs
- Chains keep growing tall, so later finds walk long paths instead of shortcutting to the root

Answer key

For grown-ups. Fold this page away before handing over the rest.

The cheapest way to connect everything W1-mt_zOJei4yCtr-s1

5 · Every tree on 6 vertices holds exactly 6 minus 1 edges.
5 · A spanning tree on 6 vertices always keeps exactly 5 edges, so 3 of the 8 edges get removed.
5 · Every tree on 6 vertices has exactly 6 - 1 = 5 edges, and Kruskal's method always stops with a tree on all 6 vertices.
Adding BC would create a loop A to B to C to A · A, B, C, and D are already one connected piece, so BC would close a loop and is skipped.
3 · The tree keeps 6 edges, so 9 minus 6 gives 3 deleted edges.
Some minimum spanning tree must include E, so adding it can never hurt · That guarantee is the cut property, and it is what makes the greedy choice safe.
It points D and E straight at A, so later finds on this chain are shorter · Path compression rewires every node on the walked path to point directly at the root A, which makes future finds faster without changing which nodes belong to the same set.
It points D and E straight at A, so later finds on this chain are shorter · Every node touched on the walk is rewired to the root without changing set membership.
Skip it, since its ends are already connected and it would close a loop · Same root means same piece, and joining one piece to itself only draws a loop.
Chains keep growing tall, so later finds walk long paths instead of shortcutting to the root · Compression is what flattens chains toward almost constant time finds.