| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2024 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Draw minimum spanning tree |
| Difficulty | Moderate -0.8 This is a straightforward application of standard MST algorithms (Kruskal's or Prim's) to a simple 4-vertex network with clearly given edge weights. Part (a) is basic graph representation, part (b) is routine MST construction, part (c) requires simple verification, and part (d) is standard LP formulation. The question requires no novel insight and follows textbook procedures throughout, making it easier than average for A-level. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06d Graphical solution: feasible region, two variables |
| Pack type | A | B | C | D | E |
| Colours | Red, orange | Red, yellow | Orange, yellow | Red, pink | Orange, pink |
| Cost \(( \pounds )\) | 1.50 | 3.00 | 4.00 | 5.25 | 6.50 |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (a) | Vertices are the 4 colours (red, yellow, orange, |
| Answer | Marks |
|---|---|
| Orange E 6.50 Pink | M1 |
| Answer | Marks |
|---|---|
| [2] | 3.3 |
| 1.1 | A network (weighted graph) with 4 vertices and 5 arcs |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (b) | Use of Prim or Kruskal |
| Arcs A, B, D or RO, RY, RP or 1.50, 3.00, 5.25 | M1 |
| Answer | Marks |
|---|---|
| [2] | 3.4 |
| 3.4 | Any spanning tree for their network, written or drawn |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (c) | No, cost of MST is £9.75 but C+D includes all |
| four colours and only costs £9.25 | B1 | 3.2b |
| Answer | Marks | Guidance |
|---|---|---|
| No, cost of MST is £9.75 but B+E includes all | B1 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (d) | Minimise 1.5A + 3B + 4C + 5.25D + 6.5E |
| Answer | Marks |
|---|---|
| 0 A, B, C, D, E | B1 |
| Answer | Marks |
|---|---|
| [5] | 2.5 |
| Answer | Marks |
|---|---|
| 1.1 | 5 variables (number of packs of each type) used consistently |
Question 5:
5 | (a) | Vertices are the 4 colours (red, yellow, orange,
pink), arcs are the 5 pack types and arc weights
are costs
Red B 3.00 Yellow
A 1.50 C 4.00
D 5.25
Orange E 6.50 Pink | M1
A1
[2] | 3.3
1.1 | A network (weighted graph) with 4 vertices and 5 arcs
cao
Vertices need to be labelled appropriately (R,Y,O,P)
Arcs need not be labelled with pack types but do need to be
weighted with appropriate costs
Ignore working for part (b) if seen
5 | (b) | Use of Prim or Kruskal
Arcs A, B, D or RO, RY, RP or 1.50, 3.00, 5.25 | M1
A1
[2] | 3.4
3.4 | Any spanning tree for their network, written or drawn
cao, written or drawn (ignore total weight if given here)
5 | (c) | No, cost of MST is £9.75 but C+D includes all
four colours and only costs £9.25 | B1 | 3.2b | Comparing cost of a valid pair (with 9.75)
C and D costs less
May imply ‘not’
Alternative solution
No, cost of MST is £9.75 but B+E includes all | B1 | B1 | B and E costs less | B and E costs less
four colours and only costs £9.50
[1]
5 | (d) | Minimise 1.5A + 3B + 4C + 5.25D + 6.5E
Subject to
A+B+C+D+E 4
A+B+D 1, B+C 1, A+C+E 1, D+E 1
0 A, B, C, D, E | B1
B1
M1
A1
B1
[5] | 2.5
3.3
3.1b
1.1
1.1 | 5 variables (number of packs of each type) used consistently
‘Minimise’ an appropriate objective function
At most 4 packs
At least one of each colour (any one of these), allow > 0
All four correct (ignore extras)
Non-negativity (or 0-1 variables)5 A garden centre sells mixed packs of flower bulbs.\\
Each pack contains bulbs which produce flowers of two different colours.
The cost, in $\pounds$, of a pack of each colour combination is shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | }
\hline
Pack type & A & B & C & D & E \\
\hline
Colours & Red, orange & Red, yellow & Orange, yellow & Red, pink & Orange, pink \\
\hline
Cost $( \pounds )$ & 1.50 & 3.00 & 4.00 & 5.25 & 6.50 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
\item Construct a minimum spanning tree for the network.
Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours.
Taylor wants to minimise the total cost of these packs.
\item Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
\item Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2024 Q5 [10]}}