Questions (33218 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure 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 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
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 PURE 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 PURE S1 S2 S3 S4 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 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 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
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2002 June Q1
5 marks Easy -1.8
1.
Ashford6
Colnbrook1
Datchet18
Feltham12
Halliford9
Laleham0
Poyle5
Staines13
Wraysbury14
The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.
Edexcel D1 2002 June Q2
6 marks Moderate -0.8
2. While solving a maximizing linear programming problem, the following tableau was obtained.
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)00\(1 \frac { 2 } { 3 }\)10\(- \frac { 1 } { 6 }\)\(\frac { 2 } { 3 }\)
\(y\)01\(3 \frac { 1 } { 3 }\)01\(- \frac { 1 } { 3 }\)\(\frac { 1 } { 3 }\)
\(x\)10-30-1\(\frac { 1 } { 2 }\)1
\(P\)00101111
  1. Explain why this is an optimal tableau.
  2. Write down the optimal solution of this problem, stating the value of every variable.
  3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
Edexcel D1 2002 June Q3
6 marks Moderate -0.8
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_483_401_489}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_478_401_1106}
\end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$
  1. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
  2. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
    \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.
Edexcel D1 2002 June Q5
11 marks Easy -1.2
5. An algorithm is described by the flow chart below. \includegraphics[max width=\textwidth, alt={}, center]{652477eb-87dc-4a5a-8514-c9be39986142-5_1590_1264_363_539}
  1. Given that \(a = 645\) and \(b = 255\), complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
  2. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
  3. State what the algorithm achieves.
Edexcel D1 2002 June Q6
12 marks Standard +0.3
6. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-6_1083_1608_421_259}
\end{figure} A building project is modelled by the activity network shown in Fig. 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. The left box entry at each vertex is the earliest event time and the right box entry is the latest event time.
  1. Determine the critical activities and state the length of the critical path.
  2. State the total float for each non-critical activity.
  3. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
  4. draw up a schedule to determine the minimum number of workers required to complete the project in the critical time. State the minimum number of workers.
    (3)
Edexcel D1 2002 June Q7
11 marks Moderate -0.5
7. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-7_719_1170_590_438}
\end{figure}
  1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
    1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
    1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.
Edexcel D1 2002 June Q8
14 marks Moderate -0.8
8. A chemical company produces two products \(X\) and \(Y\). Based on potential demand, the total production each week must be at least 380 gallons. A major customer's weekly order for 125 gallons of \(Y\) must be satisfied. Product \(X\) requires 2 hours of processing time for each gallon and product \(Y\) requires 4 hours of processing time for each gallon. There are 1200 hours of processing time available each week. Let \(x\) be the number of gallons of \(X\) produced and \(y\) be the number of gallons of \(Y\) produced each week.
  1. Write down the inequalities that \(x\) and \(y\) must satisfy.
    (3) It costs \(\pounds 3\) to produce 1 gallon of \(X\) and \(\pounds 2\) to produce 1 gallon of \(Y\). Given that the total cost of production is \(\pounds C\),
  2. express \(C\) in terms of \(x\) and \(y\).
    (1) The company wishes to minimise the total cost.
  3. Using the graphical method, solve the resulting Linear Programming problem. Find the optimal values of \(x\) and \(y\) and the resulting total cost.
  4. Find the maximum cost of production for all possible choices of \(x\) and \(y\) which satisfy the inequalities you wrote down in part (a).
Edexcel D1 2008 June Q1
8 marks Easy -1.2
1. \(\begin{array} { l l l l l l l l l } 29 & 52 & 73 & 87 & 74 & 47 & 38 & 61 & 41 \end{array}\) The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.
  1. Obtain a lower bound for the number of tapes needed to store the nine programmes.
  2. Use the first-fit bin packing algorithm to fit the programmes onto the tapes.
  3. Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes.
Edexcel D1 2008 June Q2
8 marks Moderate -0.8
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_432_579_1206_395} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_430_579_1208_1096} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5 . A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.
  1. Use the maximum matching algorithm, starting with vertex G , to increase the number of matchings. State the alternating path you used.
  2. List the improved matching you found in (a).
  3. Explain why a complete matching is not possible. Weidi agrees to be assigned to coach trip 3, 4 or 5.
  4. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching.
    (3)
Edexcel D1 2008 June Q3
9 marks Standard +0.3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-3_549_1397_258_333} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows a network of roads. The number on each arc represents the length, in km, of that road.
  1. Use Dijkstra's algorithm to find the shortest route from A to I. State your shortest route and its length.
    (5) Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A .
  2. Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route.
    (4)
    (The total weight of the network is 197 km )
Edexcel D1 2008 June Q4
8 marks Moderate -0.8
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-4_653_1257_248_404} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure}
  1. State two differences between Kruskal's algorithm and Prim's algorithm for finding a minimum spanning tree.
    (2)
  2. Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using
    1. Prim's algorithm,
    2. Kruskal's algorithm.
      (6)
Edexcel D1 2008 June Q5
11 marks Easy -1.2
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-5_819_1421_251_322} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.
  1. State the values of \(x\) and \(y\).
  2. List the saturated arcs.
  3. State the value of the feasible flow.
  4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
  5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
  6. Prove that the new flow is maximal.
Edexcel D1 2008 June Q6
10 marks Standard +0.3
6. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4\(\frac { 7 } { 3 }\)\(\frac { 5 } { 2 }\)10064
\(s\)13001016
\(t\)42200160
\(P\)-5\(\frac { - 7 } { 2 }\)-40000
  1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use.
    (9)
  2. Explain how you know that your solution is not optimal.
    (1)
Edexcel D1 2008 June Q7
14 marks Moderate -0.3
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-7_769_1385_262_342} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} The network in Figure 6 shows the activities that need to be undertaken to complete a building project. Each activity is represented by an arc. The number in brackets is the duration of the activity in days. The early and late event times are shown at each vertex.
  1. Find the values of \(v , w , x , y\) and \(z\).
  2. List the critical activities.
  3. Calculate the total float on each of activities H and J .
  4. Draw a cascade (Gantt) chart for the project. The engineer in charge of the project visits the site at midday on day 8 and sees that activity E has not yet been started.
  5. Determine if the project can still be completed on time. You must explain your answer. Given that each activity requires one worker and that the project must be completed in 35 days,
  6. use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer.
Edexcel D1 2008 June Q8
7 marks Easy -1.3
8. Class 8 B has decided to sell apples and bananas at morning break this week to raise money for charity. The profit on each apple is 20 p , the profit on each banana is 15 p . They have done some market research and formed the following constraints.
  • They will sell at most 800 items of fruit during the week.
  • They will sell at least twice as many apples as bananas.
  • They will sell between 50 and 100 bananas.
Assuming they will sell all their fruit, formulate the above information as a linear programming problem, letting \(a\) represent the number of apples they sell and \(b\) represent the number of bananas they sell. Write your constraints as inequalities.
(Total 7 marks)
Edexcel D1 2012 June Q1
12 marks Easy -1.8
  1. A carpet fitter needs the following lengths, in metres, of carpet.
$$\begin{array} { l l l l l l l l l } 20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25 \end{array}$$ He cuts them from rolls of length 50 m .
  1. Calculate a lower bound for the number of rolls he needs. You must make your method clear.
  2. Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
  3. Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
  4. Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.
Edexcel D1 2012 June Q2
7 marks Moderate -0.8
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_593_264_372} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_588_267_1096} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.
  1. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.
    (4)
  2. Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.
    (3)
Edexcel D1 2012 June Q3
7 marks Moderate -0.8
3.
ABCDEFG
A-1519-2224-
B15--813--
C19--12-16-
D-812-10-18
E2213-10-1516
F24-16-15-17
G---181617-
The table shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G.
  1. Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
  2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
  3. Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
  4. State the weight of the minimum spanning tree.
Edexcel D1 2012 June Q4
12 marks Standard +0.3
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-5_661_1525_292_269} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} \section*{[The total weight of the network is 1436 m ]}
  1. Explain the term valency. Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe. Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
  2. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
  3. Find the length of the inspection route. Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
  4. Find the length of the minimum inspection route excluding HI. Justify your answer.
  5. Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
Edexcel D1 2012 June Q5
10 marks Moderate -0.3
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-6_785_1463_191_301} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.
  1. Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.
    (6)
  2. Explain how you determined your shortest route from your labelled diagram.
    (2) Due to flooding, the roads in and out of D are closed.
  3. Find the shortest route from S to T avoiding D . State your shortest route and its length.
    (2)
Edexcel D1 2012 June Q6
14 marks Moderate -0.5
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-7_624_1461_194_301} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 is the activity network relating to a development project. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete the precedence table in the answer book.
    (2)
  2. Complete Diagram 1 in the answer book to show the early event times and late event times.
    (4)
  3. Calculate the total float for activity E. You must make the numbers you use in your calculation clear.
    (2)
  4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
    (2)
  5. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
Edexcel D1 2012 June Q7
13 marks Moderate -0.8
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-8_2491_1570_175_299} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A company is going to hire out two types of car, standard and luxury. Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy. Figure 6 shows three constraints, other than \(x , y \geqslant 0\) Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)
  1. Write, as an inequality, the third constraint shown in Figure 6. The company decides that at least \(\frac { 1 } { 6 }\) of the cars must be luxury cars.
  2. Express this information as an inequality and show that it simplifies to $$5 y \geqslant x$$ You must make the steps in your working clear. Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
  3. Express this information as an inequality.
  4. Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).
  5. Hence determine the feasible region and label it R . The company expects to make \(\pounds 80\) profit per week on each car.
    It therefore wishes to maximise \(\mathrm { P } = 80 x + 80 y\), where P is the profit per week.
  6. Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
  7. Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit.
Edexcel D1 2013 June Q1
7 marks Moderate -0.5
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_533_551_365_402} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_529_545_365_1098} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.
  1. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
  2. Explain why it is not possible to find a complete matching. After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
  3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching.
Edexcel D1 2013 June Q2
8 marks Moderate -0.8
2.
ABCDEF
A-85110160225195
B85-100135180150
C110100-215200165
D160135215-235215
E225180200235-140
F195150165215140-
The table shows the average journey time, in minutes, between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
  1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.
  2. Draw your tree using the vertices given in Diagram 1 in the answer book.
  3. Find the weight of your minimum spanning tree. Kruskal's algorithm may also be used to find a minimum spanning tree.
  4. State three differences between Prim's algorithm and Kruskal's algorithm.
Edexcel D1 2013 June Q3
12 marks Standard +0.3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-04_549_1347_258_360} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} A project is modelled by the activity network shown in Figure 3. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the 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 late event times.
  2. Calculate the total float for activity H. You must make the numbers you use in your calculation clear.
  3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. Show your calculation. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
  4. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.