Identify specific edge in algorithm

3 The following network shows the lengths, in miles, of roads connecting ten villages, \(A , B , C , \ldots , J\). \includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}

1. 1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Find the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Prim's algorithm from different starting points produces the same minimum spanning tree. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
   1. \(A\);
   2. \(F\).

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.

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}

The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
2. State the length of your minimum spanning tree. [1 mark]
3. Draw your minimum spanning tree. [3 marks]
4. If Prim's algorithm, starting at \(B\), 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 mark]