Year 11 Extended · Unit 7 Networks and vectors · Lesson 3 of 8

What is the cheapest way to connect everything, and the quickest way to get there?

A weighted graph puts a number on every edge. Two questions follow: what is the shortest route between two vertices, and what is the cheapest set of edges that joins every vertex. They sound alike, and this lesson asks whether they have the same answer.

Geometry and TrigonometryNo calculator

Warm-up

Three quick ones from earlier work. Try each in your head or on paper before you open the answer.

  1. From lesson 1: a graph has 11 edges. What do its degrees add to?
    Answer22. Each edge is counted at both ends.
  2. From Year 7: work out 4 + 6 + 2 + 5 + 1.
    Answer18.
  3. From lesson 2: a connected graph has four vertices of odd degree. Does it have an Euler route?
    AnswerNo. A route needs 0 or 2 odd vertices.
Words used in this lesson
weighted graph
a graph with a number on each edge. For example: road lengths in kilometres.
tree
a connected graph with no cycle. For example: a branching river system.
spanning tree
a tree that includes every vertex. For example: pipes to every house.
shortest path
the route with the least total weight between two vertices. For example: the quickest drive.
cycle
a route that returns to its starting vertex. For example: a ring road.

Is the cheapest way to join every village the same as the quickest road to one of them?

A water board in the hills above Kathmandu must lay pipes to six villages, A to F. The map gives the length in kilometres of each path along which a pipe could be laid. A courier also wants the shortest way from village A to the others along the same paths. Both questions use the same weighted graph. A weighted graph puts a number, the weight or length, on every edge.

Predict first: will the least total length of pipe that connects all six villages equal the length of the shortest route from A to the farthest village? Then use the figure to compare a shortest route with a minimum spanning tree.

E
route
11shortest distance from A to the chosen vertex
14weight of a minimum spanning tree

Shortest route from A to E: A, C, B, D, E with length 11.

Show me the steps
  1. Destination E, route: A, C, B, D, E has length 2 + 1 + 6 + 2 = 11, which is shorter than going A, C, E directly (2 + 10 = 12).
  2. Destination F, route: A, C, B, D, F has length 2 + 1 + 6 + 4 = 13, which beats A, C, B, D, E, F (14).
  3. Spanning tree: take BC 1, AC 2, DE 2 and EF 3 in order of weight, skip AB 4 and DF 4 because each would close a cycle, then take BD 6. Five edges join six vertices, total weight 14.
  4. The route to F (13) and the tree (14) are different numbers: the tree must reach every vertex, but the route only has to reach F.

Shortest path. Work outwards from the start, fixing the vertex that is currently closest, and update the distance to its neighbours. The route to a vertex may go the long way round if the extra steps are short: the fewest edges is not the least total length.

Minimum spanning tree. A tree is a connected graph with no cycle, and a spanning tree joins every vertex. A tree on n vertices has n − 1 edges. To find the cheapest one, take the edges in order of weight and keep each one that does not close a cycle.

Two common slips. Stopping at the first route you find: compare every route before choosing. And adding every cheap edge in a spanning tree without testing for a cycle: an edge whose ends are already joined by the edges chosen so far is skipped.

Worked examples

1. A graph has edges ST 6, SU 2, UT 3, TV 4 and UV 5. Find the shortest route from S to V.

  1. The routes are S, U, V (2 + 5 = 7); S, U, T, V (2 + 3 + 4 = 9); S, T, V (6 + 4 = 10).
  2. The shortest is S, U, V with length 7.

2. Find a minimum spanning tree of the same graph.

  1. In order of weight: SU 2, UT 3, TV 4, UV 5, ST 6. Take SU, UT and TV, which already join S, U, T and V.
  2. UV and ST would close cycles, so they are skipped: the tree has 3 edges and weight 9.

3. How many edges has a spanning tree of a network of 9 villages?

  1. A tree on n vertices has n − 1 edges.
  2. With n = 9 the tree has 8 edges.

Your go. The first step is given. Use the same graph (ST 6, SU 2, UT 3, TV 4, UV 5) to find the shortest route from S to T.

  1. List the routes from S to T: S, T directly, and S, U, T through U (also S, U, V, T through V).
  2. Add the weights along each route and compare.
Check the answer

S, T is 6 and S, U, T is 2 + 3 = 5, and S, U, V, T is 2 + 5 + 4 = 11, so the shortest route is S, U, T with length 5, even though it has more edges than the direct one.

Check before you go on

1. Five vertices P, Q, R, S and T have possible edges PQ 2, QR 3, PR 4, RS 5, QS 6 and ST 7. Which set of edges is a minimum spanning tree?

Your turn

Start at Level 1 and go as far as you can. Type negative numbers with a minus sign, for example -7. A wrong answer gets a reason, not just a cross: read it, then try again.

Level 1 · Getting started

2. The road network of 12 villages in a valley in Bhutan is a tree: it connects all the villages and has no cycle. How many roads are there?

3. Four towns have possible cables with these costs in thousands of rupees: AB 7, AC 3, AD 9, BC 4, BD 5 and CD 6. What is the total cost of the cheapest set of cables that joins all four towns?

Level 2 · Building

4. Roads join five villages P, Q, R, S and T with lengths in kilometres: PQ 6, PR 3, RQ 2, QS 4, RS 8, ST 3 and QT 9. What is the length of the shortest route from P to T?

5. Six offices U, V, W, X, Y and Z can be joined by fibre links with these costs: UV 5, UW 3, VW 4, VX 7, WX 6, WY 8, XY 2, XZ 9 and YZ 5. What is the least total cost of links that joins all six?

Level 3 · Stretch

6. A minimum spanning tree of a network of 7 vertices has total weight 31. Every edge in the network is made 3 units longer. What is the weight of a minimum spanning tree of the new network?

7. Roads join five villages P, Q, R, S and T with lengths in kilometres: PQ 6, PR 3, RQ 2, QS 4, RS 8, ST 3 and QT 9. Every road is made 2 km longer. What is the length of the shortest route from P to T now?

Something to think about

Two different edges could have the same weight. Does the minimum spanning tree have to be unique, and does its total weight depend on which of the equal edges you choose?

One way to think about it

The tree need not be unique: with equal weights you may have a choice, and different choices can give different trees. But the total weight of a minimum spanning tree is the same whichever choice you make, because every minimum spanning tree has the least possible total, so two of them cannot have different totals.

Exit ticket

8. A tank T must supply three fields P, Q and R. Possible pipes have lengths in metres TP 40, TQ 50, TR 60, PQ 20, QR 30 and PR 70. What is the least total length of pipe that connects the tank and all three fields?