ConceptConceptDocsDocuments

Pearson Edexcel IAL Mathematics D1.2 Algorithms on graphs Question Bank

Practise graph algorithms for spanning trees and shortest paths, using network tables or diagrams to state selected arcs, routes and weights.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • use Prim’s algorithm from a named start vertex and list the selected arcs in order
  • apply Dijkstra’s algorithm to obtain the shortest route and its length

Covered syllabus points

D1.2.1 - Minimum spanning treeD1.2.2 - Dijkstra’s algorithm for finding the shortest path

D1.2 - Algorithms on graphs 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 ]

D1.2 - Algorithms on graphs question 2

[Maximum number: 8]
Figure 2

Figure 2

Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.

Figure for Question D1.2 - Algorithms on graphs question 2 — Edexcel A-Level Mathematics AS

Shortest time to travel from A to J:
Quickest route from A to J:

Question (a)

(a)

Use Dijkstra's algorithm to find the shortest time needed to travel from A to J.

State the quickest route.
(6)

[ 6 ]

Question (b)

(b)

Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer.

You do not need to find the minimum spanning tree.

[ 2 ]
All question bank results loaded