Questions — Edexcel D1 (480 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 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 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 Stats 1 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 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 2018 June Q20
20
22
24
26
28
30
32
34
36
38
\end{tabular}}} &
\hline & & & & & & & & & & & & & & & & & & & &
\hline \hline & 1 & I & I & । & I & I & I & I & I & I & I & I & I & I & I & I & I & I & 1 &
\hline & 1 & I & I & I & 1 & 1 & & I & I & I & I & I & 1 & I & I & I & I & 1 & । &
\hline \multirow{7}{*}{\includegraphics[max width=\textwidth, alt={}]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-23_1401_67_1168_25} } & & & & & & & & & & & & & & & & & & & I &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & \multicolumn{19}{|r|}{\multirow[b]{2}{*}{(Total 11 marks)}} &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline \end{tabular} \end{center} 7.
\includegraphics[max width=\textwidth, alt={}]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-25_1241_1590_299_185}
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-28_2639_1830_121_121}
Edexcel D1 2019 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_429} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_1133} \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
  1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
  2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use and state your improved matching after each iteration.
    (6)
Edexcel D1 2019 June Q2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-03_716_1491_239_294} \captionsetup{labelformat=empty} \caption{Figure 3
[0pt] [The total weight of the network is 48.2]}
\end{figure} A surveyor needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Figure 3. The number on each arc represents the length of that road in miles. To check all the roads, she needs to travel along each road at least once. She wishes to minimise the total distance travelled. The surveyor's office is at F , so she starts and ends her journey at F .
  1. Find a route for the surveyor to follow. State your route and its length. You must make your method and reasoning clear. The surveyor lives at D and wonders if she can reduce the distance travelled by starting from home and inspecting all the roads on the way to her office at F .
  2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in the inspection route from D to F. You must make your method and working clear.
  3. Determine which of the two routes, the one starting at F and ending at F , or the one starting at D and ending at F , is longer. You must show your working.
Edexcel D1 2019 June Q3
3.
ABCDEFGHJ
A-385-----
B3-4------
C84--94---
D5----749-
E--9--4--7
F--474--813
G---4---4-
H---9-84-7
J----713-7-
The table above shows the lengths, in metres, of the paths between nine vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G, H and J.
  1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book.
  2. State whether your minimum spanning tree is unique. Justify your answer.
  3. Use Dijkstra's algorithm to find the length of the shortest path from A to J.
Edexcel D1 2019 June Q4
4. $$\begin{array} { l l l l l l l l l l l } 25 & 9 & 32 & 16 & 17 & 23 & 18 & 12 & 4 & 8 & 40 \end{array}$$ The numbers in the list represent the weights, in kilograms, of eleven suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 50 kg .
  1. Calculate a lower bound for the number of containers needed. You must make your method clear.
  2. Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
  3. Carry out a quick sort to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly.
  4. Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers. The two heaviest suitcases are replaced with two suitcases both of which weigh \(x \mathrm {~kg}\). It is given that the lower bound for the number of containers needed is now one less than the number found in (a).
  5. Determine the range of values for \(x\). You should make your working clear.
Edexcel D1 2019 June Q5
5.
ActivityImmediately preceding activities
A-
B-
CA
DA
EA, B
FC, D
GD
HD, E
IF, G
JF, G, H
  1. Draw the activity network described in the precedence table above, using activity on arc and exactly 4 dummies.
  2. Explain why one of the activities I or J must be critical. It is given that activity C is a critical activity.
  3. State the activities that are therefore guaranteed to be critical.
Edexcel D1 2019 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-07_1502_1659_230_210} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The vertices of the feasible region are \(A ( 4,7 ) , B ( 5,3 ) , C ( - 1,5 )\) and \(D ( - 2,1 )\).
  1. Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. The objective is to maximise \(P = 5 x + y\)
  2. Find the coordinates of the optimal vertex and the corresponding value of \(P\). The objective is changed to maximise \(Q = k x + y\)
  3. If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex.
Edexcel D1 Q2
2. Use the binary search algorithm to try to locate the name Hannah in the following alphabetical list. Clearly indicate how you selected your pivots and which part of the list is being rejected at each stage. \begin{displayquote} Adam
Ben
Charlie
Eleanor
Freya
Greg
Jenny
Richard
Toby \end{displayquote}
Edexcel D1 Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-3_780_1353_248_356} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents the distance, in metres, between eight data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G and H . The data collection points are to be linked by cables.
  1. Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
    1. Kruskal's algorithm, stating in addition any arcs you reject,
    2. Prim's algorithm, starting from A .
  2. State the minimum amount of cable needed.
  3. Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.
Edexcel D1 Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_549_586_285_356} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_545_583_287_1128} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3. The maximum matching algorithm will be used to obtain a complete matching.
  1. Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.
    (3)
  2. Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.
Edexcel D1 Q5
5.
ActivityImmediately preceding activity
A-
B\(\boldsymbol { A }\)
\(\boldsymbol { C }\)\(\boldsymbol { A }\)
DA
E\(\boldsymbol { B } \boldsymbol { C }\)
FB C
G\(\boldsymbol { D }\)
\(\boldsymbol { H }\)D
IE
\(J\)E F \(G\)
\(K\)E F \(G\)
\(\boldsymbol { L }\)I J
The precedence table shows the activities involved in planning an opening ceremony. An activity on arc network is to be drawn to model this planning process.
  1. Draw the activity network using exactly two dummies.
  2. Explain why each of the two dummies is necessary.
Edexcel D1 Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-6_757_1253_262_406} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 models a network of water pipes that need to be inspected. The number on each arc represents the length, in km , of that pipe. A machine is to be used to inspect for leaks. The machine must travel along each pipe at least once, starting and finishing at the same point, and the length of the inspection route is to be minimised.
[0pt] [The total weight of the network is 185 km ]
  1. Starting at A, use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. Given that it is now permitted to start and finish the inspection at two distinct vertices,
  2. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.
Edexcel D1 Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-7_915_1509_267_278} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 shows the possible bus journeys linking towns, S, A, B, C, D, E, F, G, H and T. Each arc represents a bus journey. The number on each arc represents the cost, in pounds, of travelling along that route.
  1. Use Dijkstra's algorithm, on the diagram in the answer book to find the cheapest route from S to T. State your cheapest route and its cost.
    (6)
  2. Explain how you determined your cheapest route from your labelled diagram. The bus journey from S to B is cancelled due to a driver's illness.
  3. Find the cheapest route from S to T that does not include SB , and state its cost.
Edexcel D1 Q8
8. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-8_1051_1385_194_365} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A company produces two products, X and Y .
Let \(x\) and \(y\) be the hourly production, in kgs, of X and Y respectively.
In addition to \(x \geqslant 0\) and \(y \geqslant 0\), two of the constraints governing the production are $$\begin{gathered} 12 x + 7 y \geqslant 840
4 x + 9 y \geqslant 720 \end{gathered}$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out. Two further constraints are $$\begin{gathered} x \geqslant 20
3 x + 2 y \leqslant 360 \end{gathered}$$
  1. Add two lines and shading to Figure 6 in your answer book to represent these inequalities.
  2. Hence determine and label the feasible region, R. The company makes a profit of 70 p and 20 p per kilogram of X and Y respectively.
  3. Write down an expression, in terms of \(x\) and \(y\), for the hourly profit, £P.
  4. Mark points A and B on your graph where A and B represent the maximum and minimum values of P respectively. Make your method clear.
    (4)
Edexcel D1 Q9
9. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-9_784_1531_242_267} \captionsetup{labelformat=empty} \caption{Figure 7}
\end{figure} Figure 7 shows an activity network. Each activity is represented by an arc and the number in brackets on each arc is the duration of the activity in days.
  1. Complete Figure 7 in the answer book showing the early and late event times.
  2. List the critical path for this network. The sum of all the activity times is 95 days and each activity requires just one worker. The project must be completed in the minimum time.
  3. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must make your method clear.
  4. On the grid in your answer book, draw a cascade (Gantt) chart for this network.
Edexcel D1 2002 November Q1
  1. Figure 1
    \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}
A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).
  1. Complete this Hamiltonian cycle.
  2. Hence use the planarity algorithm to determine if the graph is planar.
Edexcel D1 2002 November Q2
2. The precedence table for activities involved in manufacturing a toy is shown below.
ActivityPreceding activity
\(A\)-
\(B\)-
\(C\)-
\(D\)\(A\)
\(E\)\(A\)
\(F\)\(B\)
\(G\)\(B\)
\(H\)\(C , D , E , F\)
\(I\)\(E\)
\(J\)\(E\)
\(K\)\(I\)
\(L\)\(I\)
\(M\)\(G , H , K\)
  1. Draw an activity network, using activity on arc, and exactly one dummy, to model the manufacturing process.
  2. Explain briefly why it is necessary to use a dummy in this case.
Edexcel D1 2002 November Q3
3. At a water sports centre there are five new instructors. Ali (A), George ( \(G\) ), Jo ( \(J\) ), Lydia ( \(L\) ) and Nadia \(( N )\). They are to be matched to five sports, canoeing \(( C )\), scuba diving \(( D )\), surfing \(( F )\), sailing ( \(S\) ) and water skiing ( \(W\) ). The table indicates the sports each new instructor is qualified to teach.
InstructorSport
\(A\)\(C , F , W\)
\(G\)\(F\)
\(J\)\(D , C , S\)
\(L\)\(S , W\)
\(N\)\(D , F\)
Initially, \(A , G , J\) and \(L\) are each matched to the first sport in their individual list.
  1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
  2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used. Given that on a particular day \(J\) must be matched to \(D\),
  3. explain why it is no longer possible to find a complete matching.
    \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-4_720_1305_391_236} Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes \(A\), \(B , C , D , E , F , G\) and \(H\) represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe. Each pipe must be traversed at least once and the length of the inspection route must be minimised.
Edexcel D1 2002 November Q5
5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-5_763_1490_348_242}
\end{figure}
  1. Use Dijkstra's algorithm to find the shortest route from \(S\) to \(T\) in Fig. 3. Show all necessary working in the boxes in the answer booklet. State your shortest route and its length.
  2. Explain how you determined the shortest route from your labelling.
  3. It is now necessary to go from \(S\) to \(T\) via \(H\). Obtain the shortest route and its length.
Edexcel D1 2002 November Q6
6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)
  1. The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
  2. Determine the least number of bins needed.
  3. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .
Edexcel D1 2002 November Q7
7. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-6_523_1404_348_345}
\end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
  1. Write down the source vertices. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-6_525_1404_1233_345}
    \end{figure} Figure 5 shows a feasible flow through the same network.
  2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
  3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
    (6)
  4. Show the maximal flow on Diagram 2 and state its value.
  5. Prove that your flow is maximal.
Edexcel D1 2002 November Q8
8. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.
\cline { 2 - 5 } \multicolumn{1}{c|}{}ProcessingBlendingPackingProfit ( \(\pounds 100\) )
Morning blend3124
Afternoon blend2345
Evening blend4233
The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.
  1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
    (4) An initial Simplex tableau for the above situation is
    Basic
    variable
    		\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
    \(r\)32410035
    \(s\)13201020
    \(t\)24300124
    \(P\)- 4- 5- 30000
  2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
  3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
    (2)
Edexcel D1 2003 November Q1
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-02_992_1292_477_342}
\end{figure} A local council is responsible for maintaining pavements in a district. The roads for which it is responsible are represented by arcs in Fig. 1.The junctions are labelled \(A , B , C , \ldots , G\). The number on each arc represents the length of that road in km. The council has received a number of complaints about the condition of the pavements. In order to inspect the pavements, a council employee needs to walk along each road twice (once on each side of the road) starting and ending at the council offices at \(C\). The length of the route is to be minimal. Ignore the widths of the roads.
  1. Explain how this situation differs from the standard Route Inspection problem.
  2. Find a route of minimum length and state its length.
Edexcel D1 2003 November Q2
2. An electronics company makes a product that consists of components \(A , B , C , D , E\) and \(F\). The table shows which components must be connected together to make the product work. The components are all placed on a circuit board and connected by wires, which are not allowed to cross.
ComponentMust be connected to
\(A\)\(B , D , E , F\)
\(B\)\(C , D , E\)
\(C\)\(D , E\)
\(D\)\(E\)
\(E\)\(F\)
\(F\)\(B\)
  1. On the diagram in the answer book draw straight lines to show which components need to be connected.
    (1)
  2. Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
    (4)
Edexcel D1 2003 November Q3
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-04_1488_677_342_612}
\end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6. An initial matching is obtained by matching the following pairs \(A\) to \(3 , \quad B\) to \(4 , \quad C\) to \(1 , \quad F\) to 5 .
  1. Show this matching in a distinctive way on the diagram in the answer book.
  2. Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
    (5)