| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Physical space modeling |
| Difficulty | Moderate -0.8 This is a straightforward application of basic graph theory definitions (adjacency graphs, planar graphs) with routine construction tasks. It requires understanding the concept of dual graphs but involves no problem-solving, proof, or novel insight—just careful drawing and systematic application of definitions. Easier than average A-level questions which typically require multi-step calculations or algebraic manipulation. |
| Spec | 7.02k Digraphs: directed graphs, indegree and outdegree7.02l Planar graphs: planarity, subdivision, contraction |
1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.\\
(i) Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing.\\
\includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}\\
(ii) Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.\\
(iii) Repeat parts (i) and (ii) for the following map.\\
\includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}
\hfill \mbox{\textit{OCR MEI D1 2013 Q1 [8]}}