Lesson 3: Minimum connector problems

When a route is not available

SkillMinimum connector problems

Worked example

  • Complex unfamiliar

In the Western Downs network, the owner of land between Chinchilla and Miles refuses to allow the Chinchilla–Miles line (CMCM, 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.

1 of 5 steps
  1. Step 1: Delete the unavailable edge

    Remove CMCM. The remaining edges in order: KCKC 25, KTKT 42, DJDJ 46, KMKM 51, KDKD 58, CJCJ 60, DTDT 78, CDCD 82, TMTM 95.

Try a similar one

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

Method

  1. Delete an unavailable edge, or choose a compulsory edge first.

  2. Find the new minimum spanning tree and compare its weight with the original.

  3. Convert differences to costs and compare options.

Watch out for

  • Replacing CMCM with the next edge at Miles without rerunning the method. Here that happens to be KMKM, but in general the whole tree can change.

Save your progress with a free account