# Question 4:

## Part (a):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| e.g. in the practical problem each vertex must be visited at least once. In the classical problem each vertex must be visited exactly once | B2, 1, 0 | **a1B1**: Understands the difference is connected to the number of times each vertex may be visited – condone 'point' (oe) for vertex (must refer to both problems but not necessarily by name). **a2B1**: Correctly identifies which is classical (each node visited 'exactly once') and which is practical (each node visited 'at least once' but B0 for 'more than once'). Must use correct language (e.g. vertex or node) but condone singular/plural confusion |

**Total: 2 marks**

## Part (b):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| NNA starting at A: $A - B - D - F - C - G - E - A$ | B1 | **b1B1**: Correct nearest neighbour route starting at A (must return to A) – possibly stated in terms of arcs e.g. AB, BD, DF, CF, CG, EG, EA |
| $25 + 24 + 35 + 27 + 29 + 31 + 35 = 206$ (km) | B1 | **b2B1**: CAO (206) on length of route |

**Total: 2 marks**

## Part (c):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| The better upper bound is the one starting at D as it is smaller | B1dep | **c1B1dep**: CAO dependent on the correct UB in (b) – allow 'yes it is' and with some indication that this value is smaller than the one in (b) e.g. '$203 < 206$ so yes it is' scores B1 |

**Total: 1 mark**

## Part (d)(i):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| Prim's (starting at A): AB, BD, BE, EF, CF | M1 A1 | **di1M1**: Must be using Prim's algorithm not NNA. First three arcs (or all 6 nodes/numbers across top of matrix) selected correctly. First three arcs are AB, BD, BE; first six nodes are A, B, D, E, F, C. Award M1 only for a correct tree with either no working or if starting at a different node than A. **di1A1**: CAO (order of arc selection clear) – AB, BD, BE, EF, CF |
| RMST weight $= 25 + 24 + 27 + 28 + 27 = 131$ | | |

**Total: 2 marks** (combined with d(ii))

## Part (d)(ii):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| $131 + 29\text{ (CG)} + 31\text{ (EG)} = 191$ (km) | M1 A1 | **dii2M1**: Adding two least weighted arcs ($CG(29) + EG(31)$) to the length of their answer from d(i) (where $100 \leq d(i) \leq 160$) – condone if parts (d)(i) and (d)(ii) are combined together as a single part (d). **dii2A1**: CAO (191) |

**Total: 4 marks** (parts d(i) and d(ii) combined)

## Part (e):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| The better lower bound is the one found by deleting G as this is the larger of the two | B1dep | **e1B1dep**: CAO dependent on the correct LB in (d)(ii) – allow 'no it isn't' and with some indication that this value is smaller than the one in (d)(ii) e.g. '$188 < 191$ so no it isn't' scores B1 |

**Total: 1 mark**

## Part (f):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| $191 \leq \text{optimal distance} \leq 203$ | B1ft | **f1B1ft**: Their numbers correctly used, accept any inequalities or any indication of an interval from their largest of the two values (188 or d(ii)) to their smallest of the two values (203 or (b)). e.g. condone for B1 only $203 - 191 = 12$. **If the candidate's answer to (b) is less than 188 then no marks can be awarded in (f)** |
| | B1dep | **f2B1dep**: This mark is dependent on the previous B mark – CAO including correct inequalities (accept either $191 \leq \text{optimal distance} \leq 203$ or $191 < \text{optimal distance} \leq 203$) or equivalent notation e.g. $[191, 203]$ or $(191, 203]$ |

**Total: 2 marks**