Question 5:
5 | (a) | Nearest neighbour can stall | B1
[1] | 2.5 | e.g. may not find a cycle or may not find least weight cycle
BOD descriptions that do not close the cycle
Accept valid descriptions concerning the structure of the graph
but not descriptions using hypothetical weights
5 | (b) | Ad hoc method is likely to find an acceptable
solution and is quicker than checking every
possible cycle | B1
[1] | 2.4 | Solution is good enough and method is quick
Accept ‘quicker’ or ‘easier’ or ‘more efficient’, o.e.
Or any of the following o.e.
Algorithmic approach is likely to involve an exhaustive check
Algorithmic approach finds (upper and lower) bounds only (not
necessarily optimal solution)
No known algorithm (currently) (for TSP)
5 | (c) | B 5 C
2 15
6 9
A 4 D
6 7
5
F E | M1
A1
[2] | 1.1
1.1 | Correct arcs (i.e graph correct)
At most one missing or extra arc
Ignore any working for part (f)
Correct network, i.e. correct graph weighted correctly, with no
errors. Allow ambiguous placing if plausibly correct
5 | (d) | A – D – B – C – F
Stalls before visiting E | M1
A1
[2] | 1.1
1.1 | A – D – B – C – F
No E or ‘stall’ or ‘stop’ or other explicit evidence that n.n. does not
reach every vertex
5 | (e) | e.g. A – B – C – F – C – E – D – A
Length = 39(km) | M1
A1
[2] | 3.4
3.4 | Any closed route through all six vertices, using only arcs from QP
Correct length of their route, provided it is less than 50 (km)
5 | (f) | Dijkstra’s algorithm starting from F
A 6 17 B 3 11 C 2 6
17 11 6
D 4 13 E 5 13 F 1 0
21 13 13
F to B = 11 (km) and F to C = 6 (km)
F to A = 17, F to D = 13, F to E = 13 (km) | M1*
A1
M1d*
A1
A1
[5] | 3.1a
1.1
1.1
1.1
1.1 | Evidence of using Dijkstra’s algorithm
May be seen on diagram from part (c)
Need not use box format
Order of labelling not necessary
Using F as the starting vertex
Evidence of updating (at D if starting from F but e.g. at C if starting
from A)
Shortest distance F to B = 11, F to C = 6
Correct in a list or table or seen as permanent labels, o.e.
Shortest distances F to A = 17, F to D = 13, F to E = 13
Correct in a list or table or seen as permanent labels, o.e.
SC
If M0 for dependent method mark (i.e. at best M1 A1 M0) then
SCB1 for all distances correct
F to A = 17, F to B = 11, F to C = 6, F to D = 13, F to E = 13
5 | 13
5 | (g) | A B C D E F
A 6 11 4 9 17
B 6 5 2 7 11
C 11 5 7 7 6
D 4 2 7 5 13
E 9 7 7 5 13
F 17 11 6 13 13 | B1
B1
[2] | 2.1
3.1b | Ignore errors or omissions in row F and column F
Lead diagonal may be blank or ‘0’ or ‘–‘ or similar,
but not contain any non-zero values
Bold values correct (unshaded values excluding row F and col F)
All shaded values correct
5 | (h) | e.g.
BC = 5 B C
BD = 2
DE = 5 D
CF = 6
F E
AD = 4 and AB = 6
(lower bound) 18 + 10
= 28 | M1
M1
A1
[3] | 3.4
2.2a
2.2a | Any spanning tree for {B, C, D, E, F} or {A, B, C, D, E, F}
(need not be MST)
Arcs may be listed (in any order) or tree shown as a diagram
Weights are not necessary here
Use two (different) least weight arcs from A,
for example see AB and AD (and no others) or see 4+6 or see +10
or implied from final answer 28
28 cao from correct MST for {B, C, D, E, F} or {A, B, C, D, E, F}
6 | 11 | 4 | 9 | 17