Lesson 3 of 8 · 16 min
Minimum connector problems
Model practical cable, pipe and path problems as minimum spanning trees, cost them, and adapt the method when a link must be used or cannot be used.
What you will be able to do
- Recognise a minimum connector problem and model it with a weighted graph.
- Find the least total length or cost of connecting every site, and interpret it in context.
- Adapt the method when a connection must be included or is not available.
- Explain why a minimum spanning tree does not give the shortest route between two particular sites.
A power station near Chinchilla must supply substations in five Western Downs towns. Cable can run along any of the routes shown, and each kilometre of line costs the same. Power can flow through one substation to reach the next, so the network only has to be connected — no town needs its own line to the power station.
Connect everything for the least total length: that is a minimum connector problem, and its answer is a minimum spanning tree.
Possible cable routes, with lengths in kilometres. Step through Kruskal's method, or switch the method, and check the total.
Key idea
Recognising a minimum connector problem
Look for these features:
- every site must be connected to the network, directly or through other sites;
- what is minimised is the total length, cost or time of all the links together.
The vertices are the sites, the edges are the possible links and the weights are their lengths or costs. A minimum spanning tree is the cheapest network that connects them all.
Worked example
Power lines to the Western Downs
A power station () must be connected to substations at Chinchilla (), Miles (), Jandowae (), Dalby () and Tara (). The possible cable routes (km) are: 25, 42, 51, 58, 46, 60, 82, 46, 78, 95.
(a) Find the minimum length of cable needed, and the routes used.
(b) The cable costs $150 000 per kilometre to build. Find the cost of the network.
Step 1: Recognise the problem
Every substation must be connected to the power station, directly or through other substations, for the least total length. This is a minimum spanning tree problem.
Step 2: Order the edges
25, 42, 46, 46, 51, 58, 60, 78, 82, 95.
Step 3: Apply Kruskal's method
Choose (25), (42), (46) and (46). Skip (51): and are already joined through . Choose (58), which joins to the rest.
That makes 5 edges for 6 vertices, so the tree is complete.
Step 4: Total the length
km
Step 5: Cost it
Try it yourself first, then check the working one step at a time.
Answer
(a) 217 km, using the routes power station–Chinchilla, power station–Tara, Chinchilla–Miles, power station–Dalby and Dalby–Jandowae. (b) $32 550 000.
Method
Model sites as vertices and possible links as weighted edges.
Find a minimum spanning tree and its weight.
Multiply by the cost per unit, and answer in context.
Watch out for
Stopping once every town touches a chosen edge: , , and reach all six vertices, but is still cut off from the power station.
The minimum length of cable for the Western Downs network is 217 km. A cheaper line design costs $95 000 per kilometre. What would the network cost, in dollars?
Real problems come with conditions. Two are common, and both are easy to build into Kruskal's method:
- A link must be included (it already exists, or a client needs it). Choose it first, then carry on with Kruskal's method as usual, skipping edges that make a cycle with it.
- A link is not available (a landowner refuses, a river is in the way). Delete it from the graph, then find the minimum spanning tree of what is left.
Either way, the total can only stay the same or go up, and the difference is the extra cost of the condition.
Worked example
When a route is not available
In the Western Downs network, the owner of land between Chinchilla and Miles refuses to allow the Chinchilla–Miles line (, 46 km). Cable costs $150 000 per kilometre.
(a) Find the new minimum length of cable and the extra cost.
(b) The landowner then offers access for a one-off payment of $600 000. Should the power company accept? Justify your answer.
Step 1: Delete the unavailable edge
Remove . The remaining edges in order: 25, 42, 46, 51, 58, 60, 78, 82, 95.
Step 2: Apply Kruskal's method
Choose , , and (Miles must now be reached another way), then . That is 5 edges.
Step 3: Total the length
km, which is km more than before.
Step 4: Cost the difference
, so the refusal adds $750 000.
Step 5: Compare with the offer
Paying $600 000 to use costs less than the extra $750 000, saving $150 000.
The decision rests on comparing the two extra costs, not the lengths alone.
Try it yourself first, then check the working one step at a time.
Answer
(a) 222 km, an extra 5 km costing an extra $750 000. (b) Yes: paying $600 000 for access is $150 000 cheaper than building the longer network, so the company should accept (provided nothing else changes).
Method
Delete an unavailable edge, or choose a compulsory edge first.
Find the new minimum spanning tree and compare its weight with the original.
Convert differences to costs and compare options.
Watch out for
Replacing with the next edge at Miles without rerunning the method. Here that happens to be , but in general the whole tree can change.
A mine between Dalby and Tara needs the Dalby–Tara line (78 km) to be built. What is the least total length of cable that connects every town to the power station and includes the Dalby–Tara line?
Common mistake
A minimum spanning tree is not a shortest-path network
The minimum spanning tree minimises the total length of the network. The route it gives from the power station to one particular town can be longer than the shortest path. In the Western Downs tree, power reaches Miles by ––, km of line, while the direct route is only 51 km. If each town's own distance matters (for example, to limit power losses), it is a different problem.
Why does always taking the lightest safe edge work?
Split the vertices into two groups in any way you like. Every spanning tree must include at least one edge between the groups, or the groups would not be connected.
Suppose a spanning tree used a heavier crossing edge where a lighter one was available. Swap in the lighter edge and remove a crossing edge on the cycle it makes: the result is still a spanning tree, and it weighs less. So a minimum spanning tree always uses a lightest crossing edge — and that is exactly what Prim's method picks at every step (one group is the tree so far) and what Kruskal's method picks (one group is a piece it has already built).
Exam tip
In a practical question, finish in context: "The minimum length of cable is 217 km, joining the power station to Chinchilla and Tara, Chinchilla to Miles, the power station to Dalby, and Dalby to Jandowae. At $150 000 per km this costs $32 550 000."
Summary
A minimum connector problem asks for the least total length or cost of connecting every site; its solution is a minimum spanning tree.
Cost the network by multiplying the total length by the cost per unit.
A link that must be included: choose it first, then continue with Kruskal's method.
A link that is not available: delete it, then find the minimum spanning tree.
The tree minimises the total, not the distance from one site to another.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.