Question 6:
6 | (a) | D – C – F | B1
[1] | 1.1 | Allow DC, CF but not path reversed
6 | (b) | B, C, D and F have odd degree
Path starts and ends at A
Pair odd vertices
BC = 3 BD = 4 BF = 6
DF = 6 CF = 5 CD = 1
Min total = 7
56 + 7
Total weight = 63 | B1
M1
A1
[3] | 3.1a
1.1
1.1 | Seen or implied from working
Any one pairing seen (e.g. BF, CD) with correct weights or total
(e.g. 7)
63 from correct use of route inspection algorithm
6 | (c) | B has odd degree so end at another odd
vertex (C, D or F)
CD = 1 CF = 5 DF = 6
Least = 1
56 + 1
Total weight = 57 | M1
A1 | 2.1
1.1 | Arcs joining odd degree vertices, excluding B
CD = 1 is the minimum or shortest or least
57 from valid working seen
SCB1 for 57 without enough evidence for M1
Alternative method
From (b) starting and finishing at B is 63
Delete an arc from B to one of C, D, F
BC = 3, BD = 4, BF = 6
Greatest = 6 | M1 | Arcs joining B to another odd degree vertex
BF = 6 is the maximum or longest or greatest
63 – 6 = 57
Total weight = 57 | A1 ft | 57 from valid working seen, or ft (their 63) – 6
[2]
Alternative method
From (b) starting and finishing at B is 63
Delete an arc from B to one of C, D, F
BC = 3, BD = 4, BF = 6
M1
Arcs joining B to another odd degree vertex
BF = 6 is the maximum or longest or greatest
6 | (d) | (i) | e.g.
Remove vertex A and arcs incident on A
DC = 1
CB = 3
CF = 5
CE = 6 (or FE = 6)
B
F C
E D
MST with A removed has weight 15
AD = 2, AC = 3
2 + 3 + 15
Lower bound = 20 | M1
A1
M1
A1
[4] | 3.1a
1.1
3.4
1.1 | Using Prim or Kruskal to construct a tree on 5 or 6 vertices
May be implied by any tree through 5 or 6 vertices that does not
use any of AF, DE, DF (labelled diagram or arcs written or
identified)
For reference:
Finding total weight of MST with a vertex removed (o.e. such as
sum seen 1+3+5+6)
[B = 14, C = 18, D = 17, E = 11, F = 12]
Two least weight arcs from (their) removed vertex
May be implied from weights or total weight of these two
[B = 7, C = 4, D = 3, E = 12, F = 11]
A lower bound = 20 (or using their removed vertex)
[B = 21, C = 22, D = 20, E = 23, F = 23]
(ii) | A – D – C – B – F – E – A
2 + 1 + 3 + 6 + 6 + 8
Upper bound = 26 | M1
A1
[2] | 3.4
1.1 | Nearest neighbour from A written as a cycle or arcs listed in order
Allow not closed
Upper bound = 26
SC B1 final answer 26 without achieving M1
6 | (e) | This is a solution between LB and UB
There may be a better solution but it is not
worth spending time checking every
possibility
. | B1
B1
[2] | 3.2b
2.2b | The given route is a solution and could be optimal
Allow ‘this is upper bound’ or ‘(visits every vertex and) weight is
26’ or ‘(solution with) weight 26’
Practical reason why it may be good enough