Year 11 Mathematics Standard

Shortest paths and spanning trees

Two worked questions, each with its solution and marking guidelines. Tutors: get a whole lesson sheet on this topic, made for your student.

  • Questions at easy and medium levels
  • As short answer and multiple choice
  • Some with diagrams
  • New numbers every time, from 5,000+ templates across NSW Years 7 to 12
For tutors

Get a free lesson sheet

Made for your student, on any topic in Year 11 Mathematics Standard, with worked solutions and a marking guide. By email, in under a minute.

  • Their name on their copy
  • Easy, medium or hard
  • No account needed
Get my free sheet

Two worked examples

Question 12 marksMedium

The diagram shows a network of roads between five stations AA, BB, CC, DD and EE. The travel time in minutes along each road is given in the table below. There is no road between any other pair of stations.

RoadTime (min)A–B12B–C45A–C76C–D48D–E44C–E79\begin{array}{|c|c|} \hline \text{Road} & \text{Time (min)} \\ \hline \text{A--B} & 12 \\ \text{B--C} & 45 \\ \text{A--C} & 76 \\ \text{C--D} & 48 \\ \text{D--E} & 44 \\ \text{C--E} & 79 \\ \hline \end{array}

Find the total travel time, in minutes, of a minimum spanning tree for this network.

Figure

Worked solution

Triangle ABCABC has roads AB=12AB = 12, BC=45BC = 45 and AC=76AC = 76 minutes, so the longest road ACAC is left out.

Triangle CDECDE has roads CD=48CD = 48, DE=44DE = 44 and CE=79CE = 79 minutes, so the longest road CECE is left out.

The minimum spanning tree uses ABAB, BCBC, CDCD and DEDE, with total length 12+45+48+44=14912 + 45 + 48 + 44 = 149 minutes.

Answer

149149

Marking guidelines

Removes the longest road from each of the two triangles in the network, so that no cycle remains

1 mark

Adds the four remaining road times to find the total length of the tree

1 mark

Report a problem with this question.

Question 23 marksMedium

Six towns A, B, C, D, E and F are joined by the roads listed in the table. Each road can be driven in either direction, and there are no other roads.

RoadABACBDBECEDFEFLength (km)12101571585\begin{array}{c|ccccccc} \text{Road} & AB & AC & BD & BE & CE & DF & EF \\ \hline \text{Length (km)} & 12 & 10 & 15 & 7 & 15 & 8 & 5 \end{array}

Find the length, in kilometres, of the shortest route from A to F.

Figure

Worked solution

Add the road lengths for each route from A to F: ABDF=12+15+8=35ABDF = 12 + 15 + 8 = 35, ABEF=12+7+5=24ABEF = 12 + 7 + 5 = 24, ACEF=10+15+5=30ACEF = 10 + 15 + 5 = 30, ACEBDF=10+15+7+15+8=55ACEBDF = 10 + 15 + 7 + 15 + 8 = 55.

The smallest total is for route ABEF, so the shortest route has length 2424 km.

Answer

2424

Marking guidelines

Identifies every possible route from A to F

1 mark

Adds the road lengths along each route

1 mark

Selects the smallest total as the shortest route length

1 mark

Report a problem with this question.

Not affiliated with NESA.