Questions — Edexcel D2 (237 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 D2 Q4
10 marks Moderate -0.5
4. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-3_771_1479_1178_237} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} A salesman is planning a four-day trip beginning at home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses. Use dynamic programming to find the route which should maximise the salesman's net profit. State the expected profit from using this route.
(10 marks)
Edexcel D2 Q5
13 marks Moderate -0.3
5. A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job:
WindowsConservatoryDoorsGreenhouse
Team A2780881
Team B2860571
Team C3090773
Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment.
(13 marks)
Edexcel D2 Q6
14 marks Standard +0.3
6. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-5_664_1029_335_440} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.
  1. Draw a complete network showing the shortest distances between the six areas.
    (3 marks)
  2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
    (5 marks)
  3. Improve this upper bound to find an upper bound of less than 55 miles.
  4. By deleting \(A\), find a lower bound for the total length of the route.
Edexcel D2 Q7
16 marks Standard +0.3
7. Mrs. Hartley organises the tennis fixtures for her school. On one day she has to send a team of 10 players to a match against school \(A\) and a team of 6 players to a match against school \(B\). She has to select the two teams from a squad that includes 7 players who live in village \(C\), 5 players who live in village \(D\) and 8 players who live in village \(E\). Having a small budget, Mrs. Hartley wishes to minimise the total amount spent on travel. The table below shows the cost, in pounds, for one player to travel from each village to each of the schools they are competing against.
\cline { 2 - 3 } \multicolumn{1}{c|}{}\(A\)\(B\)
\(C\)23
\(D\)25
\(E\)76
  1. Use the north-west corner rule to find an initial solution to this problem.
  2. Obtain improvement indices for this initial solution.
  3. Use the stepping-stone method to obtain an optimal solution and state the pattern of transportation that this represents. \section*{Please hand this sheet in for marking}
    StageStateAction
    \multirow[t]{2}{*}{1}GGI
    HHI
    \multirow[t]{3}{*}{2}D
    DG
    DH
    E
    EG
    \(E H\)
    F
    FG
    FH
    \multirow[t]{3}{*}{3}A
    AD
    \(A E\)
    \(A F\)
    B
    BD
    BE
    \(B F\)
    C
    CD
    CE
    CF
    4Home
    Home-A
    Home-B
    Home-C
    \section*{Please hand this sheet in for marking}
    1. \includegraphics[max width=\textwidth, alt={}, center]{4e50371b-0c1c-4b4e-b21d-60858ae160df-8_662_1025_529_440}
    2. Sheet for answering question 6 (cont.)
Edexcel D2 Q1
6 marks Moderate -0.8
  1. This question should be answered on the sheet provided.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e892e87c-1c2d-4f97-ac23-41e38663d0f0-02_485_995_285_477} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.
  1. Illustrate this situation as a complete network showing the shortest distances.
    (2 marks)
  2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
    (2 marks)
  3. Interpret the tour found in part (b) in terms of the original network.
    (2 marks)
Edexcel D2 Q2
8 marks Standard +0.8
2. The payoff matrix for player \(A\) in a two-person zero-sum game with value \(V\) is shown below.
\cline { 3 - 5 } \multicolumn{2}{c|}{}\(B\)
\cline { 2 - 5 } \multicolumn{2}{c|}{}IIIIII
\multirow{3}{*}{\(A\)}I- 14- 3
\cline { 2 - 5 }II- 371
\cline { 2 - 5 }III5- 2- 1
Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).
  1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
  2. Define your decision variables.
  3. Write down the objective function in terms of your decision variables.
  4. Write down the constraints.
Edexcel D2 Q3
9 marks Standard +0.3
3. This question should be answered on the sheet provided. Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times - at \(B , C\) or \(D\), at \(E , F , G\) or \(H\) and at \(I , J\) or \(K\). \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e892e87c-1c2d-4f97-ac23-41e38663d0f0-03_764_1410_477_315} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the maximum waiting time at any one stop is as small as possible. Use dynamic programming to find the route that Arthur should use.
(9 marks)
Edexcel D2 Q4
11 marks Moderate -0.5
4. A furniture manufacturer has three workshops, \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\). Orders for rolls of fabric are to be placed with three suppliers, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). The supply, demand and cost per roll in pounds, according to which supplier each workshop uses, are given in the table below.
\(W _ { 1 }\)\(W _ { 2 }\)\(W _ { 3 }\)Available
\(S _ { 1 }\)12111730
\(S _ { 2 }\)751025
\(S _ { 3 }\)56810
Required201530
Starting with the north-west corner method of finding an initial solution, find an optimal transportation pattern which minimises the total cost. State the final solution and its total cost.
(11 marks)
Edexcel D2 Q5
11 marks Standard +0.3
5. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below.
\multirow{2}{*}{}Stage
1234
A7856
\(B\)6965
C9857
D7766
Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.
(11 marks)
Edexcel D2 Q6
13 marks Standard +0.3
6. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.
\cline { 3 - 5 } \multicolumn{2}{c|}{}\(B\)
\cline { 2 - 5 } \multicolumn{2}{c|}{}IIIIII
\multirow{3}{*}{\(A\)}I35- 2
\cline { 2 - 5 }II7- 4- 1
\cline { 2 - 5 }III9- 48
  1. Applying the dominance rule, explain, with justification, which strategy can be ignored by
    1. player \(A\),
    2. player \(B\).
  2. For the reduced table, find the optimal strategy for
    1. player \(A\),
    2. player \(B\).
  3. Find the value of the game.
Edexcel D2 Q7
17 marks Moderate -0.5
7. This question should be answered on the sheet provided. A tinned food producer delivers goods to six supermarket warehouses, \(B , C , D , E , F\) and \(G\), from its base, \(A\). The distances, in kilometres, between each location are given in the table below. \section*{Please hand this sheet in for marking}
Edexcel D2 Q1
6 marks Moderate -0.8
  1. A glazing company runs a promotion for a special type of window. As a result of this the company receives orders for 30 of these windows from business \(B _ { 1 } , 18\) from business \(B _ { 2 }\) and 22 from business \(B _ { 3 }\). The company has stocks of 20 of these windows at factory \(F _ { 1 } , 35\) at factory \(F _ { 2 }\) and 15 at factory \(F _ { 3 }\). The table below shows the profit, in pounds, that the company will make for each window it sells according to which factory supplies each business.
\cline { 2 - 4 } \multicolumn{1}{c|}{}\(B _ { 1 }\)\(B _ { 2 }\)\(B _ { 3 }\)
\(F _ { 1 }\)201417
\(F _ { 2 }\)181919
\(F _ { 3 }\)151723
The glazing company wishes to supply the windows so that the total profit is a maximum.
Formulate this information as a linear programming problem.
  1. State your decision variables.
  2. Write down the objective function in terms of your decision variables.
  3. Write down the constraints and state what each one represents.
Edexcel D2 Q2
7 marks Moderate -0.8
2. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{726bca96-7f98-4ed5-b642-f5007a958c8b-03_492_862_301_502} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.
  1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
    (2 marks)
  2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
  3. Interpret the tour found in part (b) in terms of the original network.
Edexcel D2 Q3
7 marks Moderate -0.3
3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:
  • strip the wallpaper,
  • paint the woodwork and ceiling,
  • hang the new wallpaper,
  • replace the fittings and tidy up.
The table below shows the time, in hours, that each of the friends is likely to take to complete each job.
AliceBhavinCarlDieter
Strip wallpaper5354
Paint7564
Hang wallpaper8476
Replace fittings5323
As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.
  1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
    (6 marks)
  2. Hence, find the minimum time in which the friends can redecorate the lounge.
    (1 mark)
Edexcel D2 Q4
10 marks Standard +0.3
4. This question should be answered on the sheet provided. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{726bca96-7f98-4ed5-b642-f5007a958c8b-05_727_1303_523_356} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. As her plane does not have a large fuel tank, the owner wishes to choose a route that minimises the maximum distance of any one flight. Find the route that she should use and state the maximum distance of any one stage on this route.
Edexcel D2 Q5
10 marks Moderate -0.3
5. A car-hire firm has six branches in a region. Three of the branches, \(A , B\) and \(C\), have spare cars, whereas the other three, \(D , E\) and \(F\), require cars. The total number of cars required is equal to the number of cars available. The table below shows the cost in pounds of sending one car from each branch with spares to each branch needing more cars and the number of cars available or required by each branch.
\backslashbox{Branches with spare cars}{Branches needing cars}\(D\)\(E\)\(F\)Available
\(A\)6477
B8538
C4425
Required596
  1. Use the north-west corner method to obtain a possible pattern of moving cars and find its cost. The firm wishes to minimise the cost of redistributing the cars.
  2. Calculate shadow costs for the pattern found in part (a) and improvement indices for each unoccupied cell.
  3. State, with a reason, whether or not the pattern found in part (a) is optimal.
Edexcel D2 Q6
14 marks Moderate -0.3
6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.
LeedsLiverpoolManchesterNewcastleNottinghamOxfordYork
Leeds-7140967116528
Liverpool71-311559215593
Manchester4031-1366214167
Newcastle96155136-15625078
Nottingham719262156-9478
Oxford16515514125094-172
York2893677878172-
  1. Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
    (4 marks)
    A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
  2. find an initial upper bound for the length of his journey,
  3. improve this upper bound to find an upper bound of less than 575 miles.
  4. By deleting Leeds, find a lower bound for his journey.
Edexcel D2 Q7
21 marks Challenging +1.2
7. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.
Edexcel D2 Q1
7 marks Moderate -0.8
  1. A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.
\cline { 2 - 4 } \multicolumn{1}{c|}{}LawnsHedgerowsFlower Beds
Alan44.56
Beth345
Colin3.556
The team wishes to complete the tasks in the least total time.
Formulate this information as a linear programming problem.
  1. State your decision variables.
  2. Write down the objective function in terms of your decision variables.
  3. Write down the constraints and explain what each one represents.
Edexcel D2 Q2
10 marks Moderate -0.3
2. This question should be answered on the sheet provided. A pool player is to play in four tournaments. Some of the tournaments take place simultaneously and the player has to choose one of each of the following: $$\begin{array} { l l } 1 ^ { \text {st } } \text { tournament: } & A , B \text { or } C , \\ 2 ^ { \text {nd } } \text { tournament: } & D , E \text { or } F , \\ 3 ^ { \text {rd } } \text { tournament: } & G , H \text { or } I , \\ 4 ^ { \text {th } } \text { tournament: } & J , K \text { or } L \end{array}$$ Each tournament has six rounds and the player estimates how well he will do in each tournament based on which tournament he plays before it. The table below shows his expectations with each number indicating the round he expects to reach and a "7" indicating he expects to win the tournament.
\multirow{2}{*}{}Expected performance in tournament
ABC\(D\)E\(F\)\(G\)\(H\)IJ\(K\)\(L\)
\multirow{10}{*}{Previous tournament}None533
A637
B554
C755
D533
E356
\(F\)365
G241
H322
\(I\)253
He wishes to choose the tournaments such that his worst performance is as good as possible. Use dynamic programming to find which tournaments he should play.
(10 marks)
Edexcel D2 Q3
10 marks Moderate -0.5
3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below.
FilmMusicalBalletConcert
Andrew5201218
Betty6181516
Carlos421915
Davina5161113
Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)
Edexcel D2 Q4
15 marks Standard +0.8
4. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.
\cline { 3 - 4 } \multicolumn{2}{c|}{}\(B\)
\cline { 3 - 4 }III
\multirow{2}{*}{\(A\)}I4\({ } ^ { - } 8\)
\cline { 2 - 4 }II2\({ } ^ { - } 4\)
\cline { 2 - 4 }III\({ } ^ { - } 8\)2
  1. Explain why the game does not have a saddle point.
  2. Using a graphical method, find the optimal strategy for player \(B\).
  3. Find the optimal strategy for player \(A\).
  4. Find the value of the game.
Edexcel D2 Q5
16 marks Moderate -0.5
5. A carpet manufacturer has two warehouses, \(W _ { 1 }\) and \(W _ { 2 }\), which supply carpets for three sales outlets, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). At one point \(S _ { 1 }\) requires 40 rolls of carpet, \(S _ { 2 }\) requires 23 rolls of carpet and \(S _ { 3 }\) requires 37 rolls of carpet. At this point \(W _ { 1 }\) has 45 rolls in stock and \(W _ { 2 }\) has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet:
\cline { 2 - 4 } \multicolumn{1}{c|}{}\(S _ { 1 }\)\(S _ { 2 }\)\(S _ { 3 }\)
\(W _ { 1 }\)8711
\(W _ { 2 }\)91011
The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.
  1. Use the north-west corner rule to obtain an initial solution to the problem.
  2. Calculate improvement indices for the unused routes.
  3. Use the stepping-stone method to obtain an optimal solution.
Edexcel D2 Q6
17 marks Standard +0.8
6. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{073926c5-03cc-41d4-82bf-315740ead663-6_672_984_322_431} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.
  1. By inspection, draw a complete network showing the shortest distances between the towns.
  2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
    1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
    2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
  4. By deleting \(A\), find a lower bound for the total distance travelled.
  5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}
    StagePrevious tournamentCurrent tournament
    \multirow[t]{3}{*}{1}G
    J
    K
    L
    \(H\)
    J
    K
    L
    I
    J
    K
    L
    \multirow[t]{3}{*}{2}D
    G
    H
    I
    \(E\)
    G
    H
    I
    \(F\)
    G
    H
    I
    \multirow[t]{3}{*}{3}A
    D
    E
    F
    \(B\)
    D
    E
    F
    C
    D
    E
    F
    4None
    A
    B
    C
    \section*{Please hand this sheet in for marking}
    1. \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
    2. \section*{Sheet for answering question 6 (cont.)}
      2. \(\_\_\_\_\)
    5. \(\_\_\_\_\)
Edexcel D2 Q1
Easy -1.2
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-002_675_1052_378_485}
\end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .
  1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
  2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
    (3)
  3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
    (1)
  4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
    (2)