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.

Interactive

Power for the Western Downs

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

  • 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.

5 steps

Try it yourself first, then check the working one step at a time.

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.

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

  • 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.

5 steps

Try it yourself first, then check the working one step at a time.

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.

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?

in km

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 KK–CC–MM, 25+46=7125 + 46 = 71 km of line, while the direct route KMKM 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.

Lesson 3 of 80% read

Save your progress with a free account