Lesson 3: Minimum connector problems
Power lines to the Western Downs
SkillsMinimum connector problemsFinding minimum spanning trees
Worked example
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
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.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.