CourseCourseConceptConceptDocsDocuments

Edexcel A-Level Mathematics AS D1.2.1 Minimum Spanning Tree Questions

Practise finding minimum spanning trees from networks or matrices, stating selected arcs, total weight and conditions for changed arc weights.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • use Prim’s algorithm from the stated vertex and record the order of chosen arcs
  • state the MST weight from selected arcs, a matrix, or a shortest path through all vertices
  • find conditions on x so a changed arc keeps the same unique minimum spanning tree

Edexcel A-Level Mathematics AS D1.2.1 Minimum Spanning Tree Questions question 1

[Maximum number: 4]
Table 1

Table 1

Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

Question (a)

(a)

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.

[ 3 ]

Question (b)

(b)

State the weight of the minimum spanning tree.

Table 2

Table 2

Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H.
The journey time between towns E and J is x minutes where x>28
A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.

[ 1 ]
All question bank results loaded