User interface language: English | Español

Date November 2021 Marks available 1 Reference code 21N.3.AHL.TZ0.1
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term Write down Question number 1 Adapted from N/A

Question

This question explores how graph algorithms can be applied to a graph with an unknown edge weight.


Graph W is shown in the following diagram. The vertices of W represent tourist attractions in a city. The weight of each edge represents the travel time, to the nearest minute, between two attractions. The route between A and F is currently being resurfaced and this has led to a variable travel time. For this reason, AF has an unknown travel time x minutes, where x+.

Daniel plans to visit all the attractions, starting and finishing at A. He wants to minimize his travel time.

To find a lower bound for Daniel’s travel time, vertex A and its adjacent edges are first deleted.

Daniel makes a table to show the minimum travel time between each pair of attractions.

Write down the value of

To find an upper bound for Daniel’s travel time, the nearest neighbour algorithm is used, starting at vertex A.

Consider the case where x=3.

Consider the case where x>3.

Write down a Hamiltonian cycle in W.

[1]
a.

Use Prim’s algorithm, starting at vertex B, to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.

[5]
b.i.

Hence, for the case where x<9, find a lower bound for Daniel’s travel time, in terms of x.

[2]
b.ii.

p.

[1]
c.i.

q.

[1]
c.ii.

r.

[1]
c.iii.

Use the nearest neighbour algorithm to find two possible cycles.

[3]
d.i.

Find the best upper bound for Daniel’s travel time.

[2]
d.ii.

Find the least value of x for which the edge AF will definitely not be used by Daniel.

[2]
e.i.

Hence state the value of the upper bound for Daniel’s travel time for the value of x found in part (e)(i).

[2]
e.ii.

The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at H. The sum of the weights of all the edges in graph W is (92+x).

Corinne inspects all the routes as quickly as possible and takes 2 hours.

Find the value of x during Corinne’s inspection.

[5]
f.

Markscheme

e.g. ABCDEGHFA            A1


Note: Accept any other correct answers starting at any vertex.

 

[1 mark]

a.

7 vertices, so 6 edges required for MST                       (M1)


Note: To award (M1), their 6 edges should not form a cycle.


            M1A1A1


Note: Award M1 for the first three edges in correct order, A1 for BH in correct order and A1 for all of the edges correct.


weight of MST =33            A1


Note: The final A1 can be awarded independently of previous marks.

 

[5 marks]

b.i.

lower bound =33+3+x                      (M1)

=36+x            A1

 

[2 marks]

b.ii.

p=13           A1

 

[1 mark]

c.i.

q=17           A1

 

[1 mark]

c.ii.

r=14           A1

 

[1 mark]

c.iii.

attempt to use nearest neighbour algorithm                      (M1)

any two correct cycles from
ABCDEGHFA,  AFGHBCDE(F)A,  AB(A)FGHCDE(F)A           A1A1


Note: Bracketed vertices may be omitted in candidate’s answer.
Award M1A0A1 for candidates who list two correct sequences of vertices, but omit the final vertex A.

 

[3 marks]

d.i.

use ABCDEGHFA  OR  their shortest cycle from (d)(i)                   (M1)

upper bound =43           A1

 

[2 marks]

d.ii.

cycle starts: ABCDEGHF

return to A has two options, FA=18 or x                   (M1)

hence least value of x=19           A1

 

[2 marks]

e.i.

upper bound =58           A2

 

[2 marks]

e.ii.

recognition that edges will be repeated / there are odd vertices           (M1)

BH+DG=21,  BD+GH=15,  BG+DH=21  OR  18+x           A1

recognizing BD and GH is lowest weight and is repeated           (M1)

solution to CPP =107+x           A1

x=13           A1


Note: Award M1A0M0A1A1 if only pairing BD and GH is considered, leading to a correct answer.

 

[5 marks]

f.

Examiners report

Mostly well done, although some candidates wrote down a path instead of a cycle and some candidates wrote a cycle that did not include all the vertices.

a.

Many candidates could apply the algorithm correctly to find the weight of the minimum spanning tree. A common misconception was selecting the shortest edge adjacent to the previous vertex, instead of selecting the shortest edge adjacent to the existing tree. This approach will not necessarily find the minimum spanning tree. A small number of candidates found the correct minimum spanning tree, but did not show evidence of using Prim’s algorithm, which only received partial credit; where a method/algorithm is explicit in the question, working must be seen to demonstrate that approach. Part (b)(ii) was also answered reasonably well, however several candidates did not read the instruction to give their answer in terms of x, instead choosing a specific value.

b.i.

Many candidates could apply the algorithm correctly to find the weight of the minimum spanning tree. A common misconception was selecting the shortest edge adjacent to the previous vertex, instead of selecting the shortest edge adjacent to the existing tree. This approach will not necessarily find the minimum spanning tree. A small number of candidates found the correct minimum spanning tree, but did not show evidence of using Prim’s algorithm, which only received partial credit; where a method/algorithm is explicit in the question, working must be seen to demonstrate that approach. Part (b)(ii) was also answered reasonably well, however several candidates did not read the instruction to give their answer in terms of x, instead choosing a specific value.

b.ii.

Mostly well-answered.

c.i.

Mostly well-answered.

c.ii.

Mostly well-answered.

c.iii.

Many candidates could successfully apply the nearest neighbour algorithm to find a correct cycle, but some made errors finding a second one. Part (ii) was done reasonably well, with many candidates either giving the correct answer or gaining follow-through marks for selecting their shortest cycle from part (d)(i). A small number of candidates incorrectly chose their longest cycle.

d.i.

Many candidates could successfully apply the nearest neighbour algorithm to find a correct cycle, but some made errors finding a second one. Part (ii) was done reasonably well, with many candidates either giving the correct answer or gaining follow-through marks for selecting their shortest cycle from part (d)(i). A small number of candidates incorrectly chose their longest cycle.

d.ii.

This question had a mixed response. Some candidates used the table or the graph to realize that the two choices to get from A to F are either 18 or x. Some incorrectly stated x=18. These candidates often achieved success in part (e)(ii), making the connection to their previous answer in part (d).

e.i.

This question had a mixed response. Some candidates used the table or the graph to realize that the two choices to get from A to F are either 18 or x. Some incorrectly stated x=18. These candidates often achieved success in part (e)(ii), making the connection to their previous answer in part (d).

e.ii.

A surprising number of candidates did not seem to realize this was an application of the Chinese Postman Problem and simply equated the given total weight to 120 minutes. Not only does this show a lack of understanding of the problem, but it also showed a lack of appreciation of the amount of work required to answer a 5 mark question. Out of the many candidates who recognized the need to repeat edges connecting the odd vertices, some did not show complete working to explain why they chose to connect BD and GH, only gaining partial credit.

f.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.14—Graph theory
Show 27 related questions
Topic 3—Geometry and trigonometry » AHL 3.15—Adjacency matrices and tables
Topic 3—Geometry and trigonometry

View options