AQA D1 (Decision Mathematics 1) 2007 June

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 . The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
3. To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5. Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
   From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

2

1. Use a Shell sort to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 28 & 22 & 20 & 17 & 14 & 11 & 6 & 5 \end{array}$$
2. 1. Write down the number of comparisons on the first pass.
   2. Write down the number of swaps on the first pass.
3. Find the total number of comparisons needed to rearrange the original list of 8 numbers into ascending order using a shuttle sort.
   (You do not need to perform a shuttle sort.)

3 [Figure 1, printed on the insert, is provided for use in this question.]
The following network represents the footpaths connecting 12 buildings on a university campus. The number on each edge represents the time taken, in minutes, to walk along a footpath.
\includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-03_899_1317_589_356}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(A\) to \(L\).
   2. State the corresponding route.
2. A new footpath is to be constructed. There are two possibilities:
   from \(A\) to \(D\), with a walking time of 30 minutes; or from \(A\) to \(I\), with a walking time of 20 minutes. Determine which of the two alternative new footpaths would reduce the walking time from \(A\) to \(L\) by the greater amount.
   (3 marks)

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)

5 [Figure 2, printed on the insert, is provided for use in this question.]
The Jolly Company sells two types of party pack: excellent and luxury.
Each excellent pack has five balloons and each luxury pack has ten balloons.
Each excellent pack has 32 sweets and each luxury pack has 8 sweets.
The company has 1500 balloons and 4000 sweets available.
The company sells at least 50 of each type of pack and at least 140 packs in total.
The company sells \(x\) excellent packs and \(y\) luxury packs.

1. Show that the above information can be modelled by the following inequalities. $$x + 2 y \leqslant 300 , \quad 4 x + y \leqslant 500 , \quad x \geqslant 50 , \quad y \geqslant 50 , \quad x + y \geqslant 140$$ (4 marks)
2. The company sells each excellent pack for 80 p and each luxury pack for \(\pounds 1.20\). The company needs to find its minimum and maximum total income.
   1. On Figure 2, draw a suitable diagram to enable this linear programming problem to be solved graphically, indicating the feasible region and an objective line.
   2. Find the company's maximum total income and state the corresponding number of each type of pack that needs to be sold.
   3. Find the company's minimum total income and state the corresponding number of each type of pack that needs to be sold.

6

1. Mark is staying at the Grand Hotel ( \(G\) ) in Oslo. He is going to visit four famous places in Oslo: Aker Brygge ( \(A\) ), the National Theatre ( \(N\) ), Parliament House ( \(P\) ) and the Royal Palace ( \(R\) ). The figures in the table represent the walking times, in seconds, between the places.

   	Grand Hotel ( \(G\) )	Aker Brygge (A)	National Theatre ( \(N\) )	Parliament House (P)	Royal Palace (R)
   Grand Hotel ( \(G\) )	-	165	185	65	160
   Aker Brygge (A)	165	-	155	115	275
   National Theatre ( \(N\) )	185	155	-	205	125
   Parliament House (P)	65	115	205	-	225
   Royal Palace (R)	160	275	125	225	-

   Mark is to start his tour from the Grand Hotel, visiting each place once before returning to the Grand Hotel. Mark wishes to keep his walking time to a minimum.
   1. Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
   2. By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
   3. The walking time for an optimal tour is \(T\) seconds. Use your answers to parts (a)(i) and (a)(ii) to write down a conclusion about \(T\).
2. Mark then intends to start from the Grand Hotel ( \(G\) ), visit three museums, Ibsen ( \(I\) ), Munch ( \(M\) ) and Viking ( \(V\) ), and return to the Grand Hotel. He uses public transport. The table shows the minimum travelling times, in minutes, between the places.

   \backslashbox{From}{To}	Grand Hotel ( \(G\) )	Ibsen (I)	Munch ( \(M\) )	Viking ( \(\boldsymbol { V }\) )
   Grand Hotel ( \(\boldsymbol { G }\) )	-	20	17	30
   Ibsen (I)	15	-	32	16
   Munch (M)	26	18	-	21
   Viking ( \(\boldsymbol { V }\) )	19	27	24	-

   1. Find the length of the tour \(G I M V G\).
   2. Find the length of the tour GVMIG.
   3. Find the number of different possible tours for Mark.
   4. Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.