AQA D1 June 2014 Unofficial Mark Scheme

[br]\begin{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Adjacency matrix linking} A-3; B-1,2,3; C-3,4,5; D-2,4; E-2,4 \hfill \textbf{\underline{[2]}} \\[br]\item[br]\begin{enumerate}[br]\item \text{Matching} A3, B1, C5, D2, E4 \hfill \textbf{\underline{[3]}} \\[br]\item \text{Matching} A3, B1, C5, D4, E2 \hfill \textbf{\underline{[1]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{1}[br]\item [br]\begin{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{MST:} EF, EG, GD, FI, IS, GH \hfill \textbf{\underline{[5]}} \\[br]\item \text{Length} = 485 \hfill \textbf{\underline{[1]}} \\[br]\item \text{Draw the MST} \hfill \textbf{\underline{[2]}} \\[br]\end{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Last two edges for Prim's} FI, IS \hfill \textbf{\underline{[1]}} \\[br]\item \text{Last two edges for Kruskal's} FI, GH \hfill \textbf{\underline{[2]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{2}[br]\item [br]\begin{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Box 61 at K} \hfill \textbf{\underline{[6]}} \\[br]\item A-B-E-I-K \hfill \textbf{\underline{[1]}} \\[br]\end{enumerate}[br]\item \text{Length via D} = 63 \hfill \textbf{\underline{[1]}} \\[br]\item \text{Length without I} = 64, A-B-F-J-K \hfill \textbf{\underline{[2]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{3}[br]\item [br]\begin{enumerate}[br]\item \text{Optimal length} = 94.5 \text{minutes} \hfill \textbf{\underline{[5]}} \\[br]\item[br]\begin{enumerate}[br]\item \text{Pass F twice} \hfill \textbf{\underline{[1]}} \\[br]\item \text{Pass D three times} \hfill \textbf{\underline{[1]}} \\[br]\end{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Shortest for mayor} = 85.5 \text{minutes} \hfill \textbf{\underline{[2]}} \\[br]\item \text{Start at E or G} \hfill \textbf{\underline{[1]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{4}[br]\item [br]\begin{enumerate}[br]\item \text{Draw graph, indicating FR} \hfill \textbf{\underline{[5]}} \\[br]\item[br]\begin{enumerate}[br]\item P = 30 (9, 3) \hfill \textbf{\underline{[2]}} \\[br]\item P = 29.6 (6.4, 5.6) \hfill \textbf{\underline{[2]}} \\[br]\item P = -15 (9, 3) \hfill \textbf{\underline{[2]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{5}[br]\item [br]\begin{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Best upper bound} = 30 \hfill \textbf{\underline{[1]}} \\[br]\item \text{Best lower bound} = 20 \hfill \textbf{\underline{[1]}} \\[br]\end{enumerate}[br]\item[br]\begin{enumerate}[br]\item M-L-N \text{shorter} \hfill \textbf{\underline{[1]}} \\[br]\item \text{Upper bound} = 932 \hfill \textbf{\underline{[1]}} \\[br]\item M-L-N-L-B-L-E-L-M \hfill \textbf{\underline{[2]}} \\[br]\item \text{Upper bound} = 796 \hfill \textbf{\underline{[4]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{6}[br]\item 2x + 5y + 5z \leq 120 \\ x + 2y + 2z \leq 30 \\ 2x + 3y + 4z \leq 60 \\ x \textgreater y + z \\ y \geq z \\ 17y \geq 3x + 3z \hfill \textbf{\underline{[8]}} \\[br]\end{enumerate}[br]

[br]\begin{enumerate}[br]\setcounter{enumi}{7}[br]\item [br]\begin{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Even number of odd vertices only when x is odd} \hfill \textbf{\underline{[2]}} \\[br]\item x=1, \text{draw graph} \hfill \textbf{\underline{[3]}} \\[br]\end{enumerate}[br]\item[br]\begin{enumerate}[br]\item \text{Minimum degree} = 0, \text{Maximum degree} = 9 \hfill \textbf{\underline{[2]}} \\[br]\item \text{Can't have one vertex with degree 9 and one with 0} \therefore \text{9 possible degrees, 10 vertices} \hfill \textbf{\underline{[2]}} \\[br]\end{enumerate}[br]\end{enumerate}[br]\end{enumerate}[br]