| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2018 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Bipartite graph properties |
| Difficulty | Standard +0.3 This is a straightforward Further Maths question testing basic graph theory definitions and Kruskal's/Prim's algorithm. Part (i) requires knowing that K_{3,4} has 3×4=12 arcs. Part (ii) involves counting Hamiltonian paths in a bipartite graph (alternating between sets gives 3!×4!×2 paths). Part (iii) is a standard MST algorithm application with simple arithmetic. While Further Maths content, it's mostly recall and routine application rather than problem-solving. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02e Bipartite graphs: K_{m,n} notation7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 12 | B1 [1] | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Must start at one of 1, 3, 5, 7 | B1 | May be implied from working |
| \(4 \times 3 \times 3 \times 2 \times 2 \times\) choices \(= 144\) | M1 | Using multiplicative principle; \(4! \times 3! (=144)\); Allow \(3\times3\times2\times2\times1\times1\ (=36) \Rightarrow\) B1 M1; 144 with no working or incorrect working \(\Rightarrow\) B0 M1 |
| But each path can be travelled in either direction, so \(144 \div 2 = 72\) | A1 [3] | 72, from correct working seen |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. Using Kruskal's algorithm: \(1\times2=2\); \(1\times4=4\); \(1\times6=6\) and \(2\times3=6\); \(2\times5=10\); \(3\times4=12\) forms a cycle; \(2\times7=14\); ... | B1 | Arc weights correct [at least six correct arc weights shown in a list or on a diagram] |
| B1 | Evidence of using Kruskal or Prim [K: need not list all arcs] [P: may start at any vertex] | |
| B1 [3] | These six arcs chosen (list or tree) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 42 | B1 [1] | cao |
# Question 4:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 12 | B1 [1] | cao |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Must start at one of 1, 3, 5, 7 | B1 | May be implied from working |
| $4 \times 3 \times 3 \times 2 \times 2 \times$ choices $= 144$ | M1 | Using multiplicative principle; $4! \times 3! (=144)$; Allow $3\times3\times2\times2\times1\times1\ (=36) \Rightarrow$ B1 M1; 144 with no working or incorrect working $\Rightarrow$ B0 M1 |
| But each path can be travelled in either direction, so $144 \div 2 = 72$ | A1 [3] | 72, from correct working seen |
## Part (iii)(a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. Using Kruskal's algorithm: $1\times2=2$; $1\times4=4$; $1\times6=6$ and $2\times3=6$; $2\times5=10$; $3\times4=12$ forms a cycle; $2\times7=14$; ... | B1 | Arc weights correct [at least six correct arc weights shown in a list or on a diagram] |
| | B1 | Evidence of using Kruskal or Prim [K: need not list all arcs] [P: may start at any vertex] |
| | B1 [3] | These six arcs chosen (list or tree) |
## Part (iii)(b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 42 | B1 [1] | cao |
---4 The complete bipartite graph $K _ { 3,4 }$ connects the vertices $\{ 2,4,6 \}$ to the vertices $\{ 1,3,5,7 \}$.
\begin{enumerate}[label=(\roman*)]
\item How many arcs does the graph $K _ { 3,4 }$ have?
\item Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter.
The arcs are weighted with the product of the numbers at the vertices that they join.
\item (a) Use an appropriate algorithm to find a minimum spanning tree for this network.\\
(b) Give the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2018 Q4 [8]}}