# Question 4:

## Part (a) [4 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices in network | M1 | Odd vertices are 1, 2, 3, 4 (or identify correct odd-degree nodes) |
| Consider all pairings of odd vertices and find shortest paths between each pair | M1 | |
| Select minimum weight pairing | A1 | |
| Total weight = sum of all edges + repeated edges; state route | A1 | |

## Part (b)(i) [4 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| Fourth iteration uses vertex 4 as intermediary | M1 | |
| Check $d_{ij}$ vs $d_{i4} + d_{4j}$ for all $i,j$ | M1 | |
| No entries change in distance matrix | A1 | |
| No entries change in route matrix | A1 | |

## Part (b)(ii) [3 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| From distance matrix: shortest distance from 1 to 2 = 24 | B1 | |
| From route matrix: entry (1,2) = 2, so go directly $1 \to 2$ | M1 | |
| Route: $1 \to 2$, distance 24 | A1 | Or trace through route matrix correctly |

## Part (b)(iii) [2 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete network drawn with all 10 edges showing shortest distances from matrix | B1 B1 | One mark for correct vertices/structure, one for correct distances |

## Part (b)(iv) [3 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at 1, apply nearest neighbour: $1 \to$ nearest unvisited $\to \ldots \to 1$ | M1 | |
| Correct cycle identified with length stated | A1 | |
| Interpretation in original network (route described using original edges) | B1 | |

## Part (b)(v) [4 marks]

| Answer | Marks | Guidance |
|--------|-------|----------|
| Delete vertex 1 and its arcs from complete network | M1 | |
| Find minimum spanning tree on remaining vertices {2,3,4,5} | M1 | |
| Add two smallest arcs from deleted vertex 1 | M1 | |
| State lower bound value and interpret in original network | A1 | |

These pages (7 and 8) are both blank/administrative pages from an OCR 2016 exam paper (reference 4772/01 Jun16). Page 7 is explicitly labelled **"BLANK PAGE"** and page 8 contains only the OCR copyright information footer.

**There is no mark scheme content on these pages to extract.** Could you share the pages that contain the actual mark scheme questions and answers? I'd be happy to extract and format that content for you once you provide those pages.