Lesson 3: Minimum connector problems

Power lines to the Western Downs

SkillsMinimum connector problemsFinding minimum spanning trees

Worked example

  • Complex familiar

A power station (KK) must be connected to substations at Chinchilla (CC), Miles (MM), Jandowae (JJ), Dalby (DD) and Tara (TT). The possible cable routes (km) are: KCKC 25, KTKT 42, KMKM 51, KDKD 58, CMCM 46, CJCJ 60, CDCD 82, DJDJ 46, DTDT 78, TMTM 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.

1 of 5 steps
  1. 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.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Model sites as vertices and possible links as weighted edges.

  2. Find a minimum spanning tree and its weight.

  3. Multiply by the cost per unit, and answer in context.

Watch out for

  • Stopping once every town touches a chosen edge: KCKC, KTKT, CMCM and DJDJ reach all six vertices, but {D,J}\{D, J\} is still cut off from the power station.

Save your progress with a free account