AQA Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) 2024 June

1 A connected planar graph has \(v\) vertices, \(e\) edges and \(f\) faces.
Which one of the formulae below is correct? Circle your answer.
[0pt] [1 mark]
\(v + e + f = 2\)
\(v - e + f = 2\)
\(v - e - f = 2\)
\(v + e - f = 2\)

2 Find an expression for the number of edges in the complete bipartite graph, \(K _ { m , n }\) Circle your answer.
\(\frac { m } { n }\)
\(m - n\)
\(m + n\)
\(m n\)

3 Which one of the graphs shown below is semi-Eulerian? Tick ( ✓ ) one box.
[0pt] [1 mark]
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_352_335_459_333}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_113_113_612_849}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_254_254_918_370}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_113_113_973_849}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_257_254_1272_370}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_113_113_1329_849}
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-03_250_254_1631_370}

4 The set \(S\) is defined as \(S = \{ 1,2,3,4 \}\) 4

1. Complete the Cayley Table shown below for \(S\) under the binary operation multiplication modulo 5

   \(\times _ { 5 }\)	1	2	3	4
   1
   2
   3
   4

   4
2. State the identity element for \(S\) under multiplication modulo 5 4
3. State the self-inverse elements of \(S\) under multiplication modulo 5

5 A network of roads connects the villages \(A , B , C , D , E , F\) and \(G\) The weight on each arc in the network represents the distance, in miles, between adjacent villages. The network is shown in the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-05_769_983_543_511} 5

1. Draw, in the space below, the spanning tree of minimum total length for this road network. 5
2. Find the total length of the spanning tree drawn in part (a). A Young Enterprise Company decides to sell two types of cakes at a breakfast club. The two types of cakes are blueberry and chocolate. From its initial market research, the company knows that it will:
   • sell at most 200 cakes in total
   • sell at least twice as many blueberry cakes as they will chocolate cakes
   • make 20 p profit on each blueberry cake they sell
   • make 15p profit on each chocolate cake they sell.
   The company's objective is to maximise its profit. Formulate the Young Enterprise Company's situation as a linear programming problem.

7 The binary operation ∇ is defined as $$a \nabla b = a + b + a b \text { where } a , b \in \mathbb { R }$$ 7

1. Determine if \(\nabla\) is commutative on \(\mathbb { R }\) Fully justify your answer. 7
2. Prove that ∇ is associative on \(\mathbb { R }\)

8 The diagram below shows a network of pipes.
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-08_764_1009_317_497} The uncircled numbers on each arc represent the capacity of each pipe in \(\mathrm { m } ^ { 3 } \mathrm {~s} ^ { - 1 }\)
The circled numbers on each arc represent an initial feasible flow, in \(\mathrm { m } ^ { 3 } \mathrm {~s} ^ { - 1 }\), through the network. The initial flow through pipe \(S D\) is \(x \mathrm {~m} ^ { 3 } \mathrm {~s} ^ { - 1 }\)
The initial flow through pipe \(D C\) is \(y \mathrm {~m} ^ { 3 } \mathrm {~s} ^ { - 1 }\)
The initial flow through pipe \(C B\) is \(\mathrm { z } ^ { 3 } \mathrm {~s} ^ { - 1 }\) 8

1. By considering the flows at the source and the sink, explain why \(x = 7\)
   

   8	8 Prove that the maximum flow through the network is at most \(27 \mathrm {~m} ^ { 3 } \mathrm {~s} ^ { - 1 }\)	\(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) [1 mark] \(\_\_\_\_\) \(\_\_\_\_\)

9 Robert, a project manager, and his team of builders are working on a small building project. Robert has divided the project into ten activities labelled \(A , B , C , D , E , F , G , H , I\) and \(J\) as shown in the precedence table below: 9

1. On the opposite page, construct an activity network for the project and fill in the earliest start time and latest finish time for each activity. 9
2. Robert claims that the project can be completed in 20 days.
   Comment on the validity of Robert's claim.
   \includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-11_467_440_239_534}

10 Bilal and Mayon play a zero-sum game. The game is represented by the following pay-off matrix for Bilal, where \(x\) is an integer. The game has a stable solution. 10

1. Show that there is only one possible value for \(x\)
   Fully justify your answer.
   13 10
2. State the value of the game for Bilal.