IB DP Maths Topic 10.10 Nearest-neighbour algorithm for determining an upper boundHL Paper 3

 

https://play.google.com/store/apps/details?id=com.iitianDownload IITian Academy  App for accessing Online Mock Tests and More..

Question

Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.

The weighted graph \(H\), representing the distances, measured in kilometres, between the five libraries, has the following table.

Draw the weighted graph \(H\).

[2]
a.

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

[5]
b.

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

[4]
c.
Answer/Explanation

Markscheme

complete graph on 5 vertices     A1

weights correctly marked on graph     A1

[2 marks]

a.

clear indication that the nearest-neighbour algorithm has been applied     M1

DA (or 16)     A1

AB (or 18) then BC (or 15)     A1

CE (or 17) then ED (or 19)     A1

\({\text{UB}} = 85\)     A1

[5 marks]

b.

an attempt to find the minimum spanning tree     (M1)

DA (16) then BE (17) then AB (18) (total 51)     A1

reconnect C with the two edges of least weight, namely CB (15) and CE (17)     M1

\({\text{LB}} = 83\)     A1

[4 marks]

c.

Examiners report

[N/A]

a.

[N/A]

b.

[N/A]

c.

Question

Consider the following weighted graph G.

State what feature of G ensures that G has an Eulerian trail.

[1]
a.i.

State what feature of G ensures that G does not have an Eulerian circuit.

[1]
a.ii.

Write down an Eulerian trail in G.

[2]
b.

State the Chinese postman problem.

[2]
c.i.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

[3]
c.ii.

Calculate the total weight of the solution.

[1]
c.iii.
Answer/Explanation

Markscheme

G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree      R1

[1 mark]

a.i.

G does not have an Eulerian circuit because not all vertices are of even degree      R1

[1 mark]

a.ii.

for example BAEBCEFCDF      A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

b.

to determine the shortest route (walk) around a weighted graph      A1

using each edge (at least once, returning to the starting vertex)      A1

Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.

[2 marks]

c.i.

we require the Eulerian trail in (b), (weight = 65)     (M1)

and the minimum walk FEB (15)     A1

for example BAEBCEFCDFEB    A1

Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

[3 marks]

c.ii.

total weight is (65 + 15=)80      A1

[1 mark]

c.iii.

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

b.

[N/A]

c.i.

[N/A]

c.ii.

[N/A]

c.iii.

Leave a Reply