Questions — Edexcel D1 (480 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
Edexcel D1 2015 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-5_762_965_223_550} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} [The total weight of the network is 2090]
  1. Explain why a network cannot have an odd number of vertices of odd valency. Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.
  2. Write down the vertices at which the route will start and finish.
    (1) A new road, AB , of length 130 m is built. A route of minimum length that traverses each road, including AB , needs to be found. The route must start and finish at A .
  3. Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear.
  4. Calculate the length of a possible shortest inspection route. It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB , needs to be found. The route must start at A .
  5. State the finishing point so that the length of the route is minimised. Calculate how much shorter the length of this route is compared to the length of the route in (d). You must make your method and calculations clear.
    (3)
Edexcel D1 2015 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-6_687_1171_223_447} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} The numbers on the \(17 \operatorname { arcs }\) in the network shown in Figure 5 represent the distances, in km , between nine nodes, A, B, C, D, E, F, G, H and J.
  1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
  2. Starting at G , use Prim's algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree.
  3. Find the weight of the minimum spanning tree. A connected graph V has \(n\) nodes. The sum of the degrees of all the nodes in V is \(m\). The graph T is a minimum spanning tree of V .
    1. Write down, in terms of \(m\), the number of arcs in V .
    2. Write down, in terms of \(n\), the number of \(\operatorname { arcs }\) in T .
    3. Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V.
Edexcel D1 2015 June Q6
6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(C = 2 x + 3 y\)
subject to $$\begin{aligned} x + y & \geqslant 8
x & < 8
4 y & \geqslant x
3 y & \leqslant 9 + 2 x \end{aligned}$$
  1. Add lines and shading to Diagram 1 in the answer book to represent these constraints.
  2. Hence determine the feasible region and label it R .
  3. Use the objective line (ruler) method to find the exact coordinates of the optimal vertex, V, of the feasible region. You must draw and label your objective line clearly.
  4. Calculate the corresponding value of \(C\) at V . The objective is now to maximise \(2 x + 3 y\), where \(x\) and \(y\) are integers.
  5. Write down the optimal values of \(x\) and \(y\) and the corresponding maximum value of \(2 x + 3 y\). A further constraint, \(y \leqslant k x\), where \(k\) is a positive constant, is added to the linear programming problem.
  6. Determine the least value of \(k\) for which this additional constraint does not affect the feasible region.
Edexcel D1 2015 June Q7
7.
ActivityTime taken (days)Immediately preceding activities
A5-
B7-
C8-
D5A
E7A
F10B, C
G4B, C
H9C
I8G, H
J12G, H
K7D
L10E, F, I, J
The table shows the activities required for the completion of a building project. For each activity the table shows the time taken, in days, and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-8_768_1162_1238_431} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} Figure 6 shows a partially completed activity network used to model the project. The activities are represented by the arcs and the numbers in brackets on the arcs are the times taken, in days, to complete each activity.
  1. Add activities, E, F and I, and exactly one dummy to Diagram 1 in the answer book.
  2. Complete Diagram 1 in the answer book to show the early event times and late event times.
  3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
    (2)
  4. Schedule the activities, using the minimum number of workers, so that the project is completed in the minimum time.
    (Total 13 marks)
Edexcel D1 2016 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-02_492_515_374_383} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-02_492_529_379_1160} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure}
  1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of five people, Larry (L), Monisha (M), Nina (N), Phil (P) and Theo (T), to five activities, A, B, C, D and E. Figure 2 shows an initial matching.
  2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your complete matching.
Edexcel D1 2016 June Q2
2. Draw the activity network described in the precedence table below, using activity on arc and exactly three dummies.
ActivityImmediately preceding activities
A-
B-
CA
DA
EB
FB
GA, E, F
HF
IC
JD, G
KD, G
Edexcel D1 2016 June Q3
  1. 594518553471183171542
    1. The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
    The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.
  2. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. (You should ignore wastage due to cutting.)
  3. Determine whether your solution to (b) is optimal. Give a reason for your answer.
Edexcel D1 2016 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-05_841_1201_226_431} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.
  1. Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length. On another day, Sarah wishes to travel from A to F via J.
  2. Find a route of minimal length that goes from A to F via J and state its length.
  3. Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
  4. State the length, in miles, of the minimum spanning tree.
Edexcel D1 2016 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-06_1388_1648_246_221} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} An algorithm is described by the flow chart shown in Figure 4. Given that \(x = 27\) and \(y = 5\),
  1. complete the table in the answer book to show the results obtained at each step when the algorithm is applied. Give the final output. The numbers 122 and \(\frac { 1 } { 2 }\) are to be used as inputs for the algorithm described by the flow chart.
    1. State, giving a reason, which number should be input as \(x\).
    2. State the output.
Edexcel D1 2016 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-07_684_1420_233_312} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} [The total weight of the network is 384]
Figure 5 models a network of corridors in an office complex that need to be inspected by a security guard. The number on each arc is the length, in metres, of the corresponding section of corridor. Each corridor must be traversed at least once and the length of the inspection route must be minimised. The guard must start and finish at vertex A.
  1. Use the route inspection algorithm to find the length of the shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
    (5) It is now possible for the guard to start at one vertex and finish at a different vertex. An inspection route that traverses each corridor at least once is still required.
  2. Explain why the inspection route should start at a vertex with odd degree.
    (2) The guard decides to start the inspection route at F and the length of the inspection route must still be minimised.
  3. Determine where the guard should finish. You must give reasons for your answer.
  4. State a possible route and its length.
Edexcel D1 2016 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-08_860_1383_239_342} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} The network in Figure 6 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration, in days, is shown in brackets. Each activity requires exactly one worker. The early event times and late event times are shown at each vertex. Given that the total float on activity D is 1 day,
  1. find the values of \(\boldsymbol { w } , \boldsymbol { x } , \boldsymbol { y }\) and \(\boldsymbol { z }\).
  2. On Diagram 1 in the answer book, draw a cascade (Gantt) chart for the project.
  3. Use your cascade chart to determine a lower bound for the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. It is decided that the company may use up to 36 days to complete the project.
  4. On Diagram 2 in the answer book, construct a scheduling diagram to show how the project can be completed within 36 days using as few workers as possible.
    (3)
Edexcel D1 2016 June Q8
8. Charlie needs to buy storage containers. There are two different types of storage container available, standard and deluxe. Standard containers cost \(\pounds 20\) and deluxe containers cost \(\pounds 65\). Let \(x\) be the number of standard containers and \(y\) be the number of deluxe containers. The maximum budget available is \(\pounds 520\)
  1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Three further constraints are: $$\begin{aligned} x & \geqslant 2
    - x + 24 y & \geqslant 24
    7 x + 8 y & \leqslant 112 \end{aligned}$$
  2. Add lines and shading to Diagram 1 in the answer book to represent all four constraints. Hence determine the feasible region and label it R . The capacity of a deluxe container is \(50 \%\) greater than the capacity of a standard container. Charlie wishes to maximise the total capacity.
  3. State an objective function, in terms of \(x\) and \(y\).
  4. Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V.
  5. Calculate the exact coordinates of vertex V.
  6. Determine the number of each type of container that Charlie should buy. You must make your method clear and calculate the cost of purchasing the storage containers. Write your name here
    Final output \(\_\_\_\_\)

  7. 6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-22_807_1426_121_267} \captionsetup{labelformat=empty} \caption{Figure 5
    [0pt] [The total weight of the network is 384]}
    \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-24_2651_1940_118_121}
    \includegraphics[max width=\textwidth, alt={}, center]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-25_2261_50_312_36} \section*{Q uestion 7 continued}
  8. \(\_\_\_\_\)
  9. \section*{Diagram 2} (Total 12 marks)
    □ 8.
    \includegraphics[max width=\textwidth, alt={}]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-26_1570_1591_260_189}
    Diagram 1 \section*{Q uestion 8 continued}
    \includegraphics[max width=\textwidth, alt={}]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-28_2646_1833_116_118}
Edexcel D1 2017 June Q1
  1. (a) Define the terms
    1. bipartite graph,
    2. alternating path.
      (4)
    \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_624_526_653_347} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_611_519_662_1192} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} At a hotel, six guests, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be allocated to six rooms, \(1,2,3,4,5\) and 6 . Each room needs to be allocated to exactly one guest. A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
    (b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5 . Hence find an improved matching. You must list the alternating path that you use and state your improved matching.
    (3) Guest C now has room 5 added to his possible allocations.
    (c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.
Edexcel D1 2017 June Q2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-03_920_1259_262_395} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.
  1. Use Prim's algorithm, starting at B , to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.
    (3)
  2. State the minimum cost of connecting the nine computer terminals.
    (1) It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.
  3. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.
    (3)
    (Total 7 marks)
Edexcel D1 2017 June Q3
3. \(\quad \begin{array} { l l l l l l l l l l } 42 & 21 & 15 & 16 & 35 & 10 & 31 & 11 & 27 & 39 \end{array}\)
  1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65
  2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
  3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 65 The nine distinct numbers below are to be sorted into descending order $$\begin{array} { l l l l l l l l l } 23 & 14 & 17 & \boldsymbol { x } & 21 & 18 & 8 & 20 & 11 \end{array}$$ A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & \boldsymbol { x } & 21 & 18 & 14 & 20 & 11 & 8 \end{array}$$ After the second complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & 21 & 18 & \boldsymbol { x } & 20 & 14 & 11 & 8 \end{array}$$
  4. Using this information, write down the smallest interval that must contain \(\boldsymbol { x }\). Give your answer as an inequality.
Edexcel D1 2017 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-05_999_1214_233_424} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 85]}
\end{figure} Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.
  1. Use Dijkstra's algorithm to find the shortest path from A to H. State the shortest path and its length. On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.
  2. Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.
    (5) The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.
    1. State the edges that should be repeated.
    2. State a possible route and calculate its length. You must make your method and working clear.
Edexcel D1 2017 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-06_1517_1527_226_274} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
  1. Write down the inequalities that form region \(R\).
  2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + 3 y\)
  3. Use point testing to find the optimal vertex, V, of the feasible region. The objective is changed to maximise \(Q\), where \(Q = 2 x + \lambda y\)
    Given that \(\lambda\) is a constant and V is still the only optimal vertex of the feasible region,
  4. find the range of possible values of \(\lambda\).
Edexcel D1 2017 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-08_848_1543_242_260} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
  2. Draw a Gantt chart for the project on the grid provided in the answer book.
  3. State the activities that must be happening at time 18.5 An additional activity, P , is now included in the activity network shown in Figure 6. Activity P is immediately preceded only by activity D . No activity is dependent on the completion of activity P . Each activity still requires exactly one worker and the revised project is to be completed in the shortest possible time.
  4. Explain, briefly, whether or not the revised project can be completed in the same time as the original project if the duration of activity P is
    1. 10 days
    2. 17 days
Edexcel D1 2017 June Q7
7. A caterer can make three different sizes of salad; small, medium and large. The caterer will make a total of at least 280 salads. The caterer wants at least \(35 \%\) of the salads to be small and no more than \(20 \%\) of the salads to be large. The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads. The profit on each small, medium and large salad is \(40 \mathrm { p } , 60 \mathrm { p }\) and 85 p respectively. The caterer wants to maximise his total profit. Let \(x\) represent the number of small salads, \(y\) represent the number of medium salads and \(z\) represent the number of large salads. Formulate this information as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 8 marks)
Edexcel D1 2018 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-02_1189_1531_360_267} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure}
  1. Define the terms
    1. tree,
    2. minimum spanning tree.
  2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
  3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.
Edexcel D1 2018 June Q2
2. A list of nine numbers needs to be sorted into descending order.
  1. Describe how to carry out the first pass of a bubble sort on the numbers in the list. Mayleen used a sorting algorithm to sort a list of nine numbers into descending order. Mayleen's list after the first pass through the algorithm is given below. $$\begin{array} { l l l l l l l l l } 30 & 33 & 35 & 27 & 20 & 24 & 21 & 15 & 19 \end{array}$$
  2. Explain how you know that Mayleen did not use the bubble sort algorithm. Given that Mayleen used the quick sort algorithm,
  3. write down the number that was used as a pivot for the first pass,
  4. complete the quick sort to obtain a fully sorted list in descending order. You must make your pivots clear.
  5. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60 A tenth number, 18, is added to the list of nine numbers.
  6. Determine whether it is possible to pack the ten numbers into 4 bins of size 60 . You must justify your answer.
Edexcel D1 2018 June Q3
3. (a) Draw the activity network described in the precedence table below, using activity on arc and exactly four dummies.
(5)
ActivityImmediately preceding activities
A-
B-
C-
DA
ED
FA, B
GA, B, C
HA, B, C
IE, F, G
JE, F, G
KE, F, G, H
Given that D is a critical activity,
(b) state which other activities must also be critical.
(2)
Edexcel D1 2018 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-05_812_1655_269_205} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} [The total weight of the network is 293] Figure 2 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along the corresponding road.
  1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J . State the quickest route.
    (6) The road represented by edge GJ is closed due to essential maintenance. Sahil needs to travel along all the other roads to check that they are in good repair. Sahil wishes to complete his route as quickly as possible and will start and finish at the same vertex.
  2. Use the route inspection algorithm to find the duration of Sahil's quickest route. State the edges that will need to be traversed twice. You should make your method and working clear.
    (6) Given that Sahil will start and finish at vertex C,
  3. state the number of times that Sahil will visit vertex E and vertex F in his inspection route.
    (2)
Edexcel D1 2018 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-06_648_567_273_750} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5. In an initial matching, each of three workers is allocated to a different task. For this initial matching, there are three possible alternating paths that start at C . One alternating path is $$C - 3 = S - 4 = D - 5$$ A second alternating path is $$\mathrm { C } - 1 = \mathrm { H } - 2$$
  1. Use this information to deduce the initial matching.
  2. Find the third alternating path that starts at C .
  3. List the improved matching generated by using the alternating path \(\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5\)
  4. Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
    (3)
Edexcel D1 2018 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-07_748_1419_269_324} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} A project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
  2. State the critical activities.
  3. Draw a cascade (Gantt) chart for this project on the grid in the answer book.
  4. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. (You do not need to provide a schedule of the activities.)