The cheapest way to connect everything
Tonight's idea
Six towns need joining by cable so that every town can reach every other, perhaps through others. Each possible link has a cost. Which links should be built?
Two facts come first. A loop is a waste: cut any one link of a loop and everything is still connected. So the cheapest network has no loops. And a network with no loops that joins \(n\) towns has exactly \(n - 1\) links. Start with \(n\) separate towns. Each link joins two pieces into one, so it takes \(n - 1\) links to get down to one piece.
Joseph Kruskal's method, from the 1950s:
List the links from cheapest to dearest. Go down the list and build each link, unless it would close a loop.
This is greedy: grab the cheapest thing now and never reconsider. Greed often fails. Here it always gives the cheapest total. The reason is that the dearest link in a loop is never needed, and every link the method skips is exactly that: the rest of its loop was cheaper and is already built.
Watch one: six towns
In order of cost: D–E (1) build. B–C (2) build. A–C (3) build. A–B (4) skip: A and B are already joined through C, so it would close a loop. B–E (5) build. B–D (6) skip: it would close the loop B–E–D. C–E (7) skip. D–F (8) build.
That is five links for six towns, so stop. Total cost \(1 + 2 + 3 + 5 + 8 = 19\). No other choice of links connects the towns for less.
Your turn
- (a) How many links does the cheapest network joining 10 towns have? (b) Four towns P, Q, R, S have possible links P–Q 3, Q–R 4, R–S 2, S–P 5 and P–R 6. Sketch them, run Kruskal's method and give the total cost.
- In the six-town map, the cost of B–E rises from 5 to 10. Run the method again. Which links are built, and what is the total?
- Go back to the original costs. A new town G can be linked to F for 2, to C for 4, or to A for 5. Run the method on all seven towns. What is the total now? What is surprising about it?
- Someone shows you a loop-free network for the original six towns that uses A–B (cost 4). Without knowing their other links, explain how to make it cheaper and still connected. Start by removing A–B and asking what happens to the network.
Stretch: beating the cheapest network
Four towns sit at the corners of a square of side 1 km, and cable can run along any straight line. Using only links between towns, what is the shortest network? Now add a junction at the centre of the square and join every town to it. How much cable is that?
Answers
- (a) \(10 - 1 = 9\). (b) R–S (2) build, P–Q (3) build, Q–R (4) build. That is three links for four towns, so stop. Total 9. S–P and P–R would each close a loop.
- D–E (1), B–C (2), A–C (3) build; A–B (4) skip; B–D (6) build; C–E (7) skip, since C and E are now joined through B and D; D–F (8) build. Total \(1 + 2 + 3 + 6 + 8 = 20\). B–D takes over the job B–E used to do.
- D–E (1), B–C (2), G–F (2), A–C (3) build; A–B (4) skip; G–C (4) build; B–E (5) build. Six links for seven towns, so stop. Total \(1 + 2 + 2 + 3 + 4 + 5 = 17\). An extra town made the network cheaper, down from 19. F is now reached through G for \(4 + 2 = 6\), and the 8 for D–F is no longer needed.
- Remove A–B. With no loops there was only one way from A to B, so the network falls into two pieces, one holding A and one holding B. C is in one of them. If C is with A, then B–C (2) joins the two pieces; if C is with B, then A–C (3) does. Either way, add that link. Everything is connected again and the cost has dropped by at least 1.
Stretch. Between towns, the sides cost 1 and the diagonals \(\sqrt2\), so Kruskal builds three sides: 3 km. With a junction, each town is half a diagonal from the centre, \(\tfrac{\sqrt2}{2}\) km, so the total is \(4 \times \tfrac{\sqrt2}{2} = 2\sqrt2 \approx 2.83\) km. Extra points can beat the cheapest network. Two junctions do better still, \(1 + \sqrt3 \approx 2.73\) km, and finding the best junctions is a much harder problem.