| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Bipartite graph definition or properties |
| Difficulty | Easy -1.8 This question tests only basic definitions and properties of bipartite graphs through a contextual scenario. Part (i) is graph drawing from given information, parts (ii-iii) require simple observation about traversability (essentially Eulerian path concepts), and part (iv) tests the definition that bipartite graphs cannot have edges within the same partition. All parts are recall/recognition with minimal problem-solving, making this significantly easier than average A-level maths questions. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Directed graph with at least two directed arcs, each from the top of a lift to the bottom | M1 | At least two directed arcs, each from the top of a lift to the bottom |
| All 4 correct | A1 | all 4 correct |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (Angus has to repeat all of the chairlifts.) He has to repeat A either because two ski runs deliver skiers to it, or because it serves two ski runs. | B1 | |
| He has to repeat B and C... | M1 | |
| ...either because two ski runs deliver skiers to them, or because they serve two ski runs or because of ski run 4. | A1 | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Angus has to repeat ski run 3 because he has to repeat chairlifts B and/or C (or runs 4 and 5). | M1 | run 3 |
| A1 | for explanation | |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| This would have to be represented by an arc from chairlift C to chairlift D, but in a bipartite graph an arc can only connect two elements which are not in the same set. In this case the sets are chairlifts and ski runs. | B1 | needs to be contextualised |
| [1] |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Directed graph with at least two directed arcs, each from the top of a lift to the bottom | M1 | At least two directed arcs, each from the top of a lift to the bottom |
| All 4 correct | A1 | all 4 correct |
| **[2]** | | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (Angus has to repeat all of the chairlifts.) He has to repeat A either because two ski runs deliver skiers to it, or because it serves two ski runs. | B1 | |
| He has to repeat B and C... | M1 | |
| ...either because two ski runs deliver skiers to them, or because they serve two ski runs or because of ski run 4. | A1 | |
| **[3]** | | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Angus has to repeat ski run 3 because he has to repeat chairlifts B and/or C (or runs 4 and 5). | M1 | run 3 |
| | A1 | for explanation |
| **[2]** | | |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| This would have to be represented by an arc from chairlift C to chairlift D, but in a bipartite graph an arc can only connect two elements which are not in the same set. In this case the sets are chairlifts and ski runs. | B1 | needs to be contextualised |
| **[1]** | | |
---1 The directed bipartite graph represents links between chairlifts and ski runs in one part of a ski resort. Chairlifts are represented by capital letters, and ski runs are represented by numbers. For example, chairlift A takes skiers to the tops of ski runs 1 and 2, whereas ski run 2 takes skiers to the bottom of chairlift B .\\
\includegraphics[max width=\textwidth, alt={}, center]{a27c868b-4fc4-4e82-b27f-d367b15b42c2-2_551_333_493_849}\\
(i) The incomplete map in your answer book represents the three chairlifts and ski run 2 . Complete the map by drawing in the other 4 ski runs.
Angus wants to ski all 5 ski runs, starting and finishing at the bottom of chairlift A .\\
(ii) Which chairlifts does Angus have to repeat, and why?\\
(iii) Which ski runs does Angus have to repeat, and why?
The chairlifts and ski runs shown above form only part of the resort. In fact, chairlift C also takes skiers to the bottom of chairlift $D$.\\
(iv) Why can this information not be represented in a bipartite graph?
\hfill \mbox{\textit{OCR MEI D1 2015 Q1 [8]}}