ConceptConceptDocsDocuments

Pearson Edexcel IAL Mathematics D1.3 Algorithms on graphs II Question Bank

Practise graph algorithms for route inspection and travelling salesperson problems, comparing routes, bounds and repeated arcs from network data.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • compare odd-node pairings to choose repeated arcs and calculate an inspection route length
  • use nearest neighbour routes and RMST deletions to set upper and lower route bounds
  • interpret a route as towns or arcs actually visited, including repeated roads where needed

Covered syllabus points

D1.3.1 - Algorithm for finding the shortestD1.3.2 - Practical and classicalD1.3.3 - Determination of upper and lowerD1.3.4 - nearest neighbour algorithm

D1.3 - Algorithms on graphs II question 1

[Maximum number: 8]
Figure 2

Figure 2

[The total weight of the network is 458]

Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.

Question (a)

(a)

By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice.

If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.

[ 5 ]

Question (b)

(b)

Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.

[ 3 ]

D1.3 - Algorithms on graphs II question 2

[Maximum number: 6]
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)

Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound.

Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.

[ 2 ]

Question (b)

(b)

State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer.

Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.

[ 1 ]

Question (c)

(c)

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

[ 3 ]
All question bank results loaded