Lesson 3: Minimum connector problems
When a route is not available
SkillMinimum connector problems
Worked example
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.
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).
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.