7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

17
10
14
8
13
6
4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
   1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
   2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
   3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
      2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
   4. Define the term 'matching'.
      (2)
   5. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
      (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
   6. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
      (3)
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
      [0pt] [The total weight of the network is 367 metres]}
      \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
      The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
   9. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
      \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
   10. Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
   11. Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
       (3)
       6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(\quad C = 2 x + 5 y\) subject to $$\begin{aligned} x + y & \geqslant 500 \\ 5 x + 4 y & \geqslant 4000 \\ y & \leqslant 2 x \\ y & \geqslant x - 250 \\ x , y & \geqslant 0 \end{aligned}$$
   12. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
   13. Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to \(x + y \geqslant k\) for some value of \(k\).
   14. Determine the greatest value of \(k\) for which P is still the optimal point.
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \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 activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   15. Complete Diagram 1 in the answer book to show the early event times and late event times.
   16. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
   17. Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
   18. Schedule the activities, using Grid 2 in the answer book.
       8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
       Pack B contains 30 posters and 50 flyers.
       The charity must send out at least 15000 flyers.
       The charity wants between \(40 \%\) and \(60 \%\) of the total packs produced to be Pack As.
       Posters cost 15p each and flyers cost 3p each.
       The charity wishes to minimise its costs.
       Let \(x\) represent the number of Pack As produced, and \(y\) represent the number of Pack Bs produced.
       Formulate this 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 6 marks)

1. The table shows the lengths, in km, of potential rail routes between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Use Prim's algorithm, starting from A , to find a minimum spanning tree for this table. You must list the arcs that form your tree in the order that they are selected.
2. Draw your tree using the vertices given in Diagram 1 in the answer book.
3. State the total weight of your tree.

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-004_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

1 The following network shows the lengths, in miles, of roads connecting nine villages. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}

1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
2. Find the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
4. State the number of other spanning trees that are of the same length as your answer in part (a).

3 The diagram shows 10 bus stops, \(A , B , C , \ldots , J\), in Geneva. The number on each edge represents the distance, in kilometres, between adjacent bus stops. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-03_595_1362_422_331} The city council is to connect these bus stops to a computer system which will display waiting times for buses at each of the 10 stops. Cabling is to be laid between some of the bus stops.

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 bus stops.
2. State the minimum length of cabling needed.
3. Draw your minimum spanning tree.
4. If Prim's algorithm, starting from \(A\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree.

1 The following network shows the lengths, in miles, of roads connecting 11 villages, \(A , B , \ldots , K\). \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}

1. Starting from \(G\) and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.

6 A connected graph \(G\) has five vertices and has eight edges with lengths \(8,10,10,11,13,17\), 17 and 18.

1. Find the minimum length of a minimum spanning tree for \(G\).
2. Find the maximum length of a minimum spanning tree for \(G\).
3. Draw a sketch to show a possible graph \(G\) when the length of the minimum spanning tree is 53 .

4 In Paris, there is a park where there are statues of famous people; there are many visitors each day to this park. Lighting is to be installed at nine places, \(A , B , \ldots , I\), in the park. The places have to be connected either directly or indirectly by cabling, to be laid alongside the paths, as shown in the diagram. The diagram shows the length of each path, in metres, connecting adjacent places. \includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-4_1109_1120_612_459}

1. 1. Use Prim's algorithm, starting from \(A\), to find the minimum length of cabling required.
   2. State this minimum length.
   3. Draw the minimum spanning tree.
2. A security guard walks along all the paths before returning to his starting place. Find the length of an optimal Chinese postman route for the guard.

3 A theme park has 11 rides, \(A , B , \ldots K\). The network shows the distances, in metres, between pairs of rides. The rides are to be connected by cabling so that information can be collated. The manager of the theme park wishes to use the minimum amount of cabling. \includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-03_988_1575_488_248}

1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
2. State the length of cabling required.
3. Draw your minimum spanning tree.
4. The manager decides that the edge \(A E\) must be included. Find the extra length of cabling now required to give the smallest spanning tree that includes \(A E\).

3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}

1. 1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
2. 1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
   2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).

4 The diagram shows the various ski-runs at a ski resort. There is a shop at \(S\). The manager of the ski resort intends to install a floodlighting system by placing a floodlight at each of the 12 points \(A , B , \ldots , L\) and at the shop at \(S\). The number on each edge represents the distance, in metres, between two points. \includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-04_842_830_577_607} Total of all edges \(= 1135\)

1. The manager wishes to use the minimum amount of cabling, which must be laid along the ski-runs, to connect the 12 points \(A , B , \ldots , L\) and the shop at \(S\).
   1. Starting from the shop, and showing your working at each stage, use Prim's algorithm to find the minimum amount of cabling needed to connect the shop and the 12 points.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
   4. The manager used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and the eighth edges that the manager added to his spanning tree.
2. At the end of each day a snow plough has to drive at least once along each edge shown in the diagram in preparation for the following day's skiing. The snow plough must start and finish at the point \(L\). Use the Chinese Postman algorithm to find the minimum distance that the snow plough must travel.
   (6 marks)

2 A document which is currently written in English is to be translated into six other European Union languages. The cost of translating a document varies, as it is harder to find translators for some languages. The costs, in euros, are shown in the table below.

1. 1. On the table below, showing the order in which you select the edges, use Prim's algorithm, starting from \(E\), to find a minimum spanning tree for the graph connecting \(D , E , F , G , H , I\) and \(S\).
   2. Find the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. It is given that the graph has a unique minimum spanning tree. State the final two edges that would be added to complete the minimum spanning tree in the case where:
   1. Prim's algorithm starting from \(H\) is used;
   2. Kruskal's algorithm is used. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Answer space for question 2}

      	Danish ( \(\boldsymbol { D }\) )	English ( \(\boldsymbol { E }\) )	French (F)	German ( \(G\) )	Hungarian (H)	Italian (I)	Spanish \(\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }\)
      Danish (D)	-	120	140	80	170	140	140
      English ( \(\boldsymbol { E }\) )	120	-	70	80	130	130	110
      French (F)	140	70	-	90	190	85	90
      German ( \(G\) )	80	80	90	-	110	100	100
      Hungarian (H)	170	130	190	110	-	140	150
      Italian (I)	140	130	85	100	140	-	60
      Spanish ( \(\boldsymbol { S }\) )	140	110	90	100	150	60	-

      \end{table}

2 The network below shows 8 towns, \(A , B , \ldots , H\). The number on each edge shows the length of the road, in miles, between towns. During the winter, the council treats some of the roads with salt so that each town can be safely reached on treated roads from any other town. It costs \(\pounds 30\) to treat a mile of road. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-04_876_1611_497_210}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Draw your minimum spanning tree.
   3. Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
2. On one occasion, the road from \(C\) to \(E\) is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.
   [0pt] [2 marks]

3 The network below shows vertices \(A , B , C , D\) and \(E\). The number on each edge shows the distance between vertices. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-06_563_736_402_651}

1. 1. In the case where \(x = 8\), use Kruskal's algorithm to find a minimum spanning tree for the network. Write down the order in which you add edges to your minimum spanning tree.
   2. Draw your minimum spanning tree.
   3. Write down the length of your minimum spanning tree.
2. Alice draws the same network but changes the value of \(x\). She correctly uses Kruskal's algorithm and edge \(C D\) is included in her minimum spanning tree.
   1. Explain why \(x\) cannot be equal to 7 .
   2. Write down an inequality for \(x\).

7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.

1. On Figure 1 below, use Prim's algorithm, starting from \(P\), to find a minimum spanning tree for the graph connecting \(P , Q , R , S , T\) and \(U\). State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1}

   	\(\boldsymbol { P }\)	\(\boldsymbol { Q }\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(\boldsymbol { T }\)	\(\boldsymbol { U }\)
   \(\boldsymbol { P }\)	-	14	7	11	6	12
   \(\boldsymbol { Q }\)	14	-	8	10	9	10
   \(\boldsymbol { R }\)	7	8	-	12	13	15
   \(\boldsymbol { S }\)	11	10	12	-	5	11
   \(\boldsymbol { T }\)	6	9	13	5	-	10
   \(\boldsymbol { U }\)	12	10	15	11	10	-

   \end{table}
2. Another station, \(V\), is opened. The minimum costs (in euros) of travelling to and from \(V\) to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at \(V\) and visit all the other stations, once only, before returning to \(V\).
   1. By first removing \(V\), obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
   2. Use the nearest neighbour algorithm twice, starting each time from \(V\), to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
   3. Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2(ii)}

      	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)	\(V\)
      \(\boldsymbol { P }\)	-	14	7	11	6	12	15
      \(Q\)	14	-	8	10	9	10	18
      \(\boldsymbol { R }\)	7	8	-	12	13	15	14
      \(\boldsymbol { S }\)	11	10	12	-	5	11	14
      \(T\)	6	9	13	5	-	10	17
      \(\boldsymbol { U }\)	12	10	15	11	10	-	12
      \(V\)	15	18	14	14	17	12	-

      \end{table}

2 Four of the five students Phil, Quin, Ros, Sue and Tim are to be chosen to make up a team for a mathematical relay race. The team will be asked four questions, one each on the topics A, B, C and D. A different member of the team will answer each question. Each member has to give the correct answer to the question before the next question is asked. The team with the least overall time wins.
The average times, in seconds, for each student in some practice questions are given below.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first, then rows, to decide which four students should be chosen for the team. State which student should be allocated to each topic and state the total time for the four students on the practice questions using this matching.

2 The daily costs, in pounds, for five managers A, B, C, D and E to travel to five different centres are recorded in the table below. Using the Hungarian algorithm, each of the five managers is to be allocated to a different centre so that the overall total travel cost is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   3	6	3	6	0
   4	0	6	0	2
   6	4	3	6	0
   2	3	8	3	0
   0	2	0	0	2

2. Show that the zeros in the table in part (a) can be covered with three lines and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five managers to the five centres with the least possible total travel cost.
4. Find the value of this minimum daily total travel cost.

2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games. Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(20 - x\).
2. Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.

   3	1	1	1	0
   0	4	5	2	2
   4	0	5	0	7
   5	1	0	1	1
   5	1	0	2	5

3. Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of games to the five people so that the total score is maximised.
5. State the value of the maximum total score.

3 Five lecturers were given the following scores when matched against criteria for teaching five courses in a college. Each lecturer is to be allocated to exactly one of the courses so as to maximise the total score of the five lecturers.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(17 - x\).
2. Form a new table by subtracting each number in the table above from 17. Hence show that, by reducing rows first and then columns, the resulting table of values is as below.

   0	0	3	3	0
   4	3	4	0	2
   0	6	7	2	2
   5	2	3	0	6
   3	1	0	2	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of courses to the five lecturers so that the total score is maximised.
5. State the value of the maximum total score.

2 The times taken in minutes for five people, Ann, Baz, Cal, Di and Ez, to complete each of five different tasks are recorded in the table below. Neither Ann nor Di can do task 2, as indicated by the asterisks in the table.

6 An animal sanctuary has a rainwater collection site. The manager of the sanctuary is installing a pipe system to connect the rainwater collection site to five other sites in the sanctuary. Each site does not need to be connected directly to the rainwater collection site. There are nine possible routes between the sites that are suitable for water pipes. The distances, in metres, of the nine possible routes are given in the table below. Water pipe costs 60 pence per metre. Find the minimum cost of connecting all the sites to the rainwater collection site. Fully justify your answer. \(7 \quad\) A linear programming problem has the constraints $$\begin{aligned} 1 \leq x & \leq 6 \\ 1 \leq y & \leq 6 \\ y & \geq x \\ x + y & \leq 11 \end{aligned}$$

6 A garden has seven statues \(A , B , C , D , E , F\) and \(G\), with paths connecting each pair of statues, either directly or indirectly. To provide better access to all the statues, some of the paths are being made wider.
6

1. State why six is the minimum number of paths that need to be made wider. 6
2. The table below shows the number of trees that need to be removed to make the path between adjacent statues wider. A dash in the table means that there is no direct path between the two statues.

   Statue	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	C	\(\boldsymbol { D }\)	\(E\)	\(F\)	\(G\)
   \(\boldsymbol { A }\)	-	4	7	-	-	-	-
   B	4	-	6	2	3	-	-
   C	7	6	-	-	3	-	4
   \(D\)	-	2	-	-	4	5	-
   \(E\)	-	3	3	4	-	3	7
   \(F\)	-	-	-	5	3	-	6
   G	-	-	4	-	7	6	-

   Find the minimum number of trees that need to be removed. Fully justify your answer.
   6
3. A landscaper identifies that two new wide paths could be constructed without removing any trees. However, there are only enough resources to build one new wide path. The new wide path could be between \(A\) and \(D\) or between \(A\) and \(F\).
   Explain clearly how the solution to part (b) can be adapted to find the new minimum number of trees that need to be removed.
   [0pt] [2 marks]

7 A construction company has built eight wind turbines on a moorland site. The network below shows nodes which represent the site entrance, \(E\), and the wind turbine positions, \(S , T , \ldots , Z\) \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-12_924_1294_479_356} Each arc represents an access track with its length given in metres.
These 17 tracks were created in order to build the wind turbines. Eight of the tracks are to be retained so that each turbine can be accessed for maintenance, directly or indirectly, from the site entrance. The other nine tracks will be removed. 7

1. 1. To save money the construction company wants to maximise the total length of the eight tracks to be retained. Determine which tracks the construction company should retain.
      7
      1. (ii) Find the total length of the eight tracks that are to be retained. 7
   2. The total length of the 17 tracks is 14.6 km
      The cost of removing all 17 tracks would be \(\pounds 87,600\) Using your answer to part (a)(ii), calculate an estimate for the cost of removing the nine tracks that will not be retained.
      [0pt] [2 marks]
      7
   3. Comment on why the modelling used in part (b) may not give an accurate estimate for the cost of removing the nine tracks.

3 A company is installing an internal telephone network between the offices in a council building. Each office is required to be connected with telephone cables, either directly or indirectly, to every other office in the building. The lengths of cable, in metres, needed to connect the offices are shown in the table below. The council wants the total length of cable that is used to be as small as possible.
The cost to the council to install one metre of cable is \(\pounds 8\) 3

1. 1. Find the minimum total cost to the council to install the cable required for the internal telephone network.
      [0pt] [4 marks]
      3
      1. (ii) Suggest a reason why the total cost to the council for installing the internal telephone network is likely to be different from your answer to part (a)(i). 3
   2. Before the company starts installing the cable, it is told that the Education office cannot be connected directly to the Transport office due to issues with the building. Explain the possible impact of this on your answer to part (a)(i).