OCR D2 (Decision Mathematics 2) 2005 June

1 [Answer this question on the insert provided.]
The network below represents a system of pipelines through which fluid flows from \(S\) to \(T\). The capacities of the pipelines, in litres per second, are shown as weights on the arcs.
\includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}

1. Write down the arcs from \(\{ S , A , C , E \}\) to \(\{ B , D , F , T \}\). Hence find the capacity of the cut that separates \(\{ S , A , C , E \}\) from \(\{ B , D , F , T \}\).
2. On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.
3. Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.
4. Use the maximum flow - minimum cut theorem to show that the maximum flow from \(S\) to \(T\) is 13 litres per second.
5. \(E B\) is replaced by a pipeline with capacity 2 litres per second from \(B\) to \(E\). Find the new maximum flow from \(S\) to \(T\). You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.

2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song. Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.

1. Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( \(1,2,3,4\) and 5 ) on the right hand side. The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
2. Explain why this would not be a satisfactory way to allocate the songs.
3. Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
4. Find a different allocation in which each of the five contestants is given a song that they chose. Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters. The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).

   \multirow{2}{*}{}	Character
   	Fire Chief	Gardener	Handyman	Juggler	King
   Adam	4	9	7	0	7
   Bex	6	8	3	8	0
   Chris	7	4	5	2	7
   Denny	6	6	2	7	1

   The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
5. Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
6. Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.

3 The table lists the activities involved in preparing for a cycle ride, their expected durations and their immediate predecessors.

1. Draw an activity network to represent the information in the table. Show the activities on the arcs and indicate the direction of each activity and dummy activity. You are advised to make your network quite large.
2. Carry out a forward pass and a backward pass to determine the minimum completion time for preparing for the ride. List the critical activities.
3. Construct a cascade chart, showing each activity starting at its earliest possible time. Two people, John and Kerry, are intending to go on the cycle ride. Activities \(A , B , F\) and \(G\) will each be done by just one person (either John or Kerry), but both are needed (at the same time) for activities \(C , D\) and \(E\). Also, each of John and Kerry must carry out activity \(H\), although not necessarily at the same time. All timings and precedences in the original table still apply.
4. Draw up a schedule showing which activities are done by each person at which times in order to complete preparing for the ride in the shortest time possible. The schedule should have three columns, the first showing times in 4-minute intervals, the second showing which activities John does and the third showing which activities Kerry does.

4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( \(5 ; 0\) ) and the exit as ( \(0 ; 0\) ). He then counted the numbers of plants along paths. These numbers are shown below.

1. Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
2. Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.