Questions — AQA D1 (167 questions)

Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
AQA D1 2010 June Q5
5 Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G , I , N , R , S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point.
\(\boldsymbol { G }\)\(\boldsymbol { I }\)\(N\)\(\boldsymbol { R }\)\(\boldsymbol { S }\)\(T\)
\(\boldsymbol { G }\)-8182867276
\(\boldsymbol { I }\)81-80826873
\(\boldsymbol { N }\)8280-847074
\(\boldsymbol { R }\)868284-7470
\(\boldsymbol { S }\)72687074-64
\(T\)7673747064-
  1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time.
  2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a).
  3. By deleting \(S\), find a lower bound for Phil's minimum walking time.
    \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-11_2484_1709_223_153}
AQA D1 2010 June Q6
6 Phil is to buy some squash balls for his club. There are three different types of ball that he can buy: slow, medium and fast. He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast balls. He must buy at least 300 balls in total.
Each slow ball costs \(\pounds 2.50\), each medium ball costs \(\pounds 2.00\) and each fast ball costs \(\pounds 2.00\). He must spend no more than \(\pounds 1000\) in total.
At least \(60 \%\) of the balls that he buys must be slow balls.
Phil buys \(x\) slow balls, \(y\) medium balls and \(z\) fast balls.
  1. Find six inequalities that model Phil's situation.
  2. Phil decides to buy the same number of medium balls as fast balls.
    1. Show that the inequalities found in part (a) simplify to give $$x \geqslant 190 , y \geqslant 50 , x + 2 y \geqslant 300,5 x + 8 y \leqslant 2000 , y \leqslant \frac { 1 } { 3 } x$$
    2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for \(\pounds 3.00\), each medium ball for \(\pounds 2.25\) and each fast ball for \(\pounds 2.25\). He wishes to maximise his profit. On Figure 1 on page 14, draw a diagram to enable this problem to be solved graphically, indicating the feasible region and the direction of an objective line.
      (7 marks)
    3. Find Phil's maximum possible profit and state the number of each type of ball that he must buy to obtain this maximum profit.
      \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-13_2484_1709_223_153}
      \includegraphics[max width=\textwidth, alt={}, center]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-15_2484_1709_223_153}
      \(7 \quad\) A student is testing a numerical method for finding an approximation for \(\pi\).
      The algorithm that the student is using is as follows.
      Line 10 Input \(A , B , C , D , E\)
      Line 20 Let \(A = A + 2\)
      Line 30 Let \(B = - B\)
      Line \(40 \quad\) Let \(C = \frac { B } { A }\)
      Line 50 Let \(D = D + C\)
      Line \(60 \quad\) Let \(E = ( D - 3.14 ) ^ { 2 }\)
      Line 70 If \(E < 0.05\) then go to Line 90
      Line 80 Go to Line 20
      Line 90 Print ' \(\pi\) is approximately', \(D\)
      Line 100 End Trace the algorithm in the case where the input values are $$A = 1 , B = 4 , C = 0 , D = 4 , E = 0$$ (6 marks)
      \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-17_2484_1707_223_155}
AQA D1 2010 June Q8
8 A simple connected graph has six vertices.
  1. One vertex has degree \(x\). State the greatest and least possible values of \(x\).
  2. The six vertices have degrees $$x - 2 , x - 2 , x , 2 x - 4,2 x - 4,4 x - 12$$ Find the value of \(x\), justifying your answer.
    \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-19_2484_1707_223_155}
AQA D1 2011 June Q1
1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.
123456
\(\boldsymbol { A }\)101000
\(\boldsymbol { B }\)110001
C010100
\(\boldsymbol { D }\)010010
E001010
F000010
  1. Represent this information in a bipartite graph.
  2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.
AQA D1 2011 June Q2
2 Five different integers are to be sorted into ascending order.
  1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
  2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
  3. Use your answers from parts (a) and (b) to write down the value of \(x\).
AQA D1 2011 June Q3
3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table.
\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)\(\boldsymbol { F }\)\(\boldsymbol { G }\)\(\boldsymbol { H }\)
\(\boldsymbol { A }\)-15101216111417
\(\boldsymbol { B }\)15-151415161615
\(\boldsymbol { C }\)1015-111012149
\(\boldsymbol { D }\)121411-11121412
\(\boldsymbol { E }\)16151011-131514
\(\boldsymbol { F }\)1116121213-148
G141614141514-13
\(\boldsymbol { H }\)171591214813-
One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.
    1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the table.
    2. Draw your minimum spanning tree.
    3. Find the minimum total cost.
  1. Person \(H\) leaves the group. Find the new minimum total cost.
AQA D1 2011 June Q4
4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway. Carol, the headteacher, wishes to walk from her office ( \(O\) ) to the Drama department (D) .
    1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(O\) to \(D\).
    2. Write down the corresponding route.
  1. On another occasion, Carol needs to go from her office to the Business Studies department \(( B )\).
    1. Write down her minimum walking time.
    2. Write down the route corresponding to this minimum time.
      \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}
AQA D1 2011 June Q5
5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point \(A\), and must drive along all the roads at least once before returning to the depot.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}
  1. Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at \(A\).
  2. Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point \(A\), and drives along all the roads at least once before finishing at his home, located at point \(C\). Find the length of an optimal route for Zac.
  3. Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
    1. Find the length of an optimal route for Liz.
    2. State the points from which Liz could start in order to achieve this optimal route.
      \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}
AQA D1 2011 June Q6
6 A student is tracing the following algorithm.
Line 10 Let \(A = 6\)
Line \(20 \quad\) Let \(B = 7\)
Line 30 Input \(C\)
Line 40 Let \(D = ( A + B ) / 2\)
Line \(50 \quad\) Let \(E = C - D ^ { 3 }\)
Line 60 If \(E ^ { 2 } < 1\) then go to Line 120
Line 70 If \(E > 0\) then go to Line 100
Line 80 Let \(B = D\)
Line 90 Go to Line 40
Line \(100 \quad\) Let \(A = D\)
Line 110 Go to Line 40
Line 120 Stop
  1. Trace the algorithm in the case where the input value is \(C = 300\).
  2. The algorithm is intended to find the approximate cube root of any input number. State two reasons why the algorithm is unsatisfactory in its present form.
    (3 marks)
AQA D1 2011 June Q7
7 A builder needs some screws, nails and plugs. At the local store, there are packs containing a mixture of the three items. A DIY pack contains 200 nails, 200 screws and 100 plugs.
A trade pack contains 1000 nails, 1500 screws and 2500 plugs.
A DIY pack costs \(\pounds 2.50\) and a trade pack costs \(\pounds 15\).
The builder needs at least 5000 nails, 6000 screws and 4000 plugs.
The builder buys \(x\) DIY packs and \(y\) trade packs and wishes to keep his total cost to a minimum.
  1. Formulate the builder's situation as a linear programming problem.
    1. On the grid opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of an objective line.
    2. Use your diagram to find the number of each type of pack that the builder should buy in order to minimise his cost.
    3. Find the builder's minimum cost.
AQA D1 2011 June Q8
8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}
    1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
    2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
    1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
    2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
  1. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Table 1}
    \(\boldsymbol { P }\)\(Q\)\(\boldsymbol { R }\)\(\boldsymbol { S }\)\(T\)\(\boldsymbol { U }\)
    \(P\)-25
    \(Q\)25-20212311
    \(\boldsymbol { R }\)20-
    \(\boldsymbol { S }\)21-
    \(T\)23-12
    \(\boldsymbol { U }\)1112-
    \end{table}
    \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}
AQA D1 2012 June Q1
1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}
  1. Represent this information in an adjacency matrix.
  2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
    (3 marks)
AQA D1 2012 June Q2
2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.
AQA D1 2012 June Q3
3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\).
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388}
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}
    1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
    2. State the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
  1. Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
    1. starting from \(D\);
    2. starting from \(H\).
AQA D1 2012 June Q4
4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.
    1. Use Dijkstra's algorithm on the network to find the shortest possible driving time from \(A\) to \(J\).
    2. Write down the corresponding route.
  1. A new ring road is to be constructed connecting \(A\) to \(J\) directly. Find the maximum length of this new road from \(A\) to \(J\) if the time taken to drive along it, travelling at an average speed of \(90 \mathrm {~km} / \mathrm { h }\), is to be no more than the time found in part (a)(i). } \section*{(a)(i)} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}
AQA D1 2012 June Q5
5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres. Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex \(B\). Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant.
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340} The total length of the streets is 2430 metres.
  1. Find the length of an optimal Chinese postman route for Tony.
  2. Colin also wishes to distribute some leaflets. He starts from his house at \(H\), walks along all the streets at least once, before finishing at the restaurant at \(B\). Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
  3. David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
    1. Find the length of an optimal route for David.
    2. State the vertices from which David could start in order to achieve this optimal route.
AQA D1 2012 June Q6
6 The complete graph \(K _ { n } ( n > 1 )\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.
  1. Draw the complete graph \(K _ { 4 }\).
    1. Find the total number of edges for the graph \(K _ { 8 }\).
    2. Give a reason why \(K _ { 8 }\) is not Eulerian.
  2. For the graph \(K _ { n }\), state in terms of \(n\) :
    1. the total number of edges;
    2. the number of edges in a minimum spanning tree;
    3. the condition for \(K _ { n }\) to be Eulerian;
    4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.
AQA D1 2012 June Q7
7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.
AQA D1 2012 June Q8
8 The following algorithm finds an estimate of the value of the number represented by the symbol e:
Line 10Let \(A = 1 , B = 1 , C = 1\)
Line 20Let \(D = A\)
Line 30Let \(C = C \times B\)
Line 40Let \(D = D + ( 1 / C )\)
Line 50If \(B = 4\) then go to Line 80
Line 60Let \(B = B + 1\)
Line 70Go to Line 30
Line 80Print 'An estimate of e is', \(D\)
Line 90End
  1. Trace the algorithm.
  2. A student miscopied Line 70 . His line was
    Line 70 Go to Line 10
    Explain what would happen if his algorithm were traced.
AQA D1 2012 June Q9
9 Ollyin is buying new pillows for his hotel. He buys three types of pillow: soft, medium and firm. He must buy at least 100 soft pillows and at least 200 medium pillows.
He must buy at least 400 pillows in total.
Soft pillows cost \(\pounds 4\) each. Medium pillows cost \(\pounds 3\) each. Firm pillows cost \(\pounds 4\) each.
He wishes to spend no more than \(\pounds 1800\) on new pillows.
At least \(40 \%\) of the new pillows must be medium pillows.
Ollyin buys \(x\) soft pillows, \(y\) medium pillows and \(z\) firm pillows.
  1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find five inequalities in \(x , y\) and \(z\) that model the above constraints.
  2. Ollyin decides to buy twice as many soft pillows as firm pillows.
    1. Show that three of your answers in part (a) become $$\begin{aligned} 3 x + 2 y & \geqslant 800
      2 x + y & \leqslant 600
      y & \geqslant x \end{aligned}$$
    2. On the grid opposite, draw a suitable diagram to represent Ollyin's situation, indicating the feasible region.
    3. Use your diagram to find the maximum total number of pillows that Ollyin can buy.
    4. Find the number of each type of pillow that Ollyin can buy that corresponds to your answer to part (b)(iii).
      \includegraphics[max width=\textwidth, alt={}]{1258a6d3-558a-46dc-a916-d71f71b175ff-20_2256_1707_221_153}
AQA D1 2013 June Q1
1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.
PersonTask
Andy1,3
Bob1,4
Colin2,3
Dev\(4,5,6\)
Eric\(2,5,6\)
Faisal1,3
  1. Represent this information on a bipartite graph.
  2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.
AQA D1 2013 June Q2
2
  1. Use the quicksort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. You must indicate the pivot(s) being used on each pass. $$2 , \quad 12 , \quad 17 , \quad 18 , \quad 5 , \quad 13$$
  2. For the first pass, write down the number of comparisons.
AQA D1 2013 June Q3
3 The following network shows the lengths, in miles, of roads connecting ten villages, \(A , B , C , \ldots , J\).
\includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}
    1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
    2. Find the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
  1. Prim's algorithm from different starting points produces the same minimum spanning tree. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
    1. \(A\);
    2. \(F\).
AQA D1 2013 June Q4
4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.
\cline { 2 - 7 } \multicolumn{1}{c|}{}\(\boldsymbol { A }\)\(\boldsymbol { B }\)\(\boldsymbol { C }\)\(\boldsymbol { D }\)\(\boldsymbol { E }\)\(\boldsymbol { F }\)
\(\boldsymbol { A }\)-1511142712
\(\boldsymbol { B }\)15-13192415
\(\boldsymbol { C }\)1113-101912
\(\boldsymbol { D }\)141910-2615
\(\boldsymbol { E }\)27241926-27
\(\boldsymbol { F }\)1215121527-
  1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
  2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
  3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
  4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
  5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.
AQA D1 2013 June Q5
5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, \(A , B , \ldots , L\). On a particular day, there are three police cars in the area at \(A , E\) and \(J\). There is an emergency at \(G\) and all three police cars drive to \(G\).
    1. Use Dijkstra's algorithm on the network, starting from \(\boldsymbol { G }\), to find the minimum driving time for each of the police cars to arrive at \(G\).
    2. For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
  1. Each day, a police car has to drive along each road at least once, starting and finishing at \(A\). For an optimal Chinese postman route:
    1. find the driving time for the police car;
    2. state the number of times that the vertex \(B\) would appear.
      \includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}