CourseCourseConceptConceptDocsDocuments

Edexcel A-Level Mathematics AS D1.2 Algorithms on Graphs Questions

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

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 ]

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 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 ]

Question 3

[Maximum number: 9]
Figure 5

Figure 5

Figure 5 shows a weighted graph that contains 12 arcs and 8 vertices.

It is given that
- no two arcs have the same weight
- x and y are positive integers
- arc CD is not in the minimum spanning tree for the graph

Question (a)

(a)

Explain why y<x+7

It is also given that when Prim's algorithm, starting at A, is applied to the weighted graph, AB is the first arc selected.

[ 2 ]

Question (b)

(b)

Show that y>2 x and write down and simplify two further constraints on the values of x and y.

[ 3 ]

Question (c)

(c)

Determine the value of x and the value of y. You must make your method and working clear.

[ 4 ]
All question bank results loaded