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)