Draw minimum spanning tree

5 A garden centre sells mixed packs of flower bulbs.
Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.

1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.

5. \section*{Question 5 continued} \section*{D} A

• \({ } ^ { \text {B } }\)
• F \(\stackrel { \bullet } { \mathrm { H } }\)

Diagram 1

A network of roads connects the villages \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) The weight on each arc in the network represents the distance, in miles, between adjacent villages. The network is shown in the diagram below. \includegraphics{figure_5}

1. Draw, in the space below, the spanning tree of minimum total length for this road network. [3 marks]
2. Find the total length of the spanning tree drawn in part (a). [1 mark]