| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Network and route modeling |
| Difficulty | Easy -1.8 This is a very basic graph theory question requiring only simple diagram drawing and recall of definitions (simple graph, tree). No calculations, algorithms, or problem-solving are needed—just direct application of elementary D1 concepts with minimal steps. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected |
| Answer | Marks | Guidance |
|---|---|---|
| Four nodes A, B, C, D with arcs: A-B, A-C (bus); B-D, C-D, A-C (train) | B2 | Award B1 for 4 correct nodes, B1 for all 5 arcs correctly drawn. Penalise extra arcs. |
| Answer | Marks | Guidance |
|---|---|---|
| No — there are two arcs connecting A and C (one bus, one train) | B1 for "No" | B1 for correct reason (multiple arc/not simple because A-C appears twice) |
| Answer | Marks | Guidance |
|---|---|---|
| Five nodes: A, B, C(bus), C(train), D with arcs: A-B, A-C(bus) [bus]; B-D, C(train)-D, A-C(train) [train]; C(bus)-C(train) [connecting the two C nodes] | B2 | B1 for correct nodes, B1 for correct arcs |
| Answer | Marks | Guidance |
|---|---|---|
| Yes — it is a tree because it is connected and has 5 nodes and 4 arcs (i.e. \(n-1\) arcs), with no cycles | B1 for "Yes" | B1 for correct justification (connected, no cycles, or \(n-1\) arcs) |
# Question 1:
## Part (i)
Four nodes A, B, C, D with arcs: A-B, A-C (bus); B-D, C-D, A-C (train) | B2 | Award B1 for 4 correct nodes, B1 for all 5 arcs correctly drawn. Penalise extra arcs.
## Part (ii)
No — there are two arcs connecting A and C (one bus, one train) | B1 for "No" | B1 for correct reason (multiple arc/not simple because A-C appears twice)
## Part (iii)
Five nodes: A, B, C(bus), C(train), D with arcs: A-B, A-C(bus) [bus]; B-D, C(train)-D, A-C(train) [train]; C(bus)-C(train) [connecting the two C nodes] | B2 | B1 for correct nodes, B1 for correct arcs
## Part (iv)
Yes — it is a tree because it is connected and has 5 nodes and 4 arcs (i.e. $n-1$ arcs), with no cycles | B1 for "Yes" | B1 for correct justification (connected, no cycles, or $n-1$ arcs)
---1 Bus routes connect towns A and B and towns A and C .\\
Train lines connect towns B and D, towns C and D, and towns A and C.\\
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.\\
(i) Draw John's graph.\\
(ii) Is John's graph simple? Justify your answer.
Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.\\
(iii) Draw Jamil's graph.\\
(iv) Is Jamil's graph a tree? Justify your answer.
\hfill \mbox{\textit{OCR MEI D1 2007 Q1 [8]}}