# Question 4:

## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial distance matrix with correct direct distances (e.g. $d_{12}=15$, $d_{14}=8+7=$ via reading graph, $\infty$ where no direct route) | B2 | B1 one error |
| Initial route matrix with $d_{ij}=j$ for all direct connections | B2 | B1 one error |

## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Fourth iteration uses node 4 as intermediate | M1 | |
| Updated distances: e.g. $d_{13}$: check via 4; $d_{35}$ via 4 etc. | M1 | |
| Correct updated distance matrix | A1 | |
| Correct updated route matrix | A1 | |

## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Read distance matrix: row 3, col 1 gives shortest distance | B1 | |
| Distance = 42 km (or value from completed matrix) | B1 | |
| Route matrix: row 3 col 1 gives next node; trace through route matrix | M1 | |
| Route traced correctly e.g. $3 \to 2 \to 1$ or similar using route matrix entries | A1 | |
| Clear explanation of how route matrix is used to trace path | B1 | |

## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete network drawn with 5 nodes, correct shortest distances as edge weights, no loops | B1 | |
| All edges correct | B1 | |

## Part (v)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Start at 2, nearest unvisited neighbour selected at each stage | M1 | |
| Correct sequence of vertices visited | A1 | |
| Correct total length of Hamilton cycle stated | A1 | |
| Interpretation: this represents a travelling salesman tour visiting each city once | B1 | |
| Statement of what achieved (upper bound for TSP on original network) | B1 | |