Edexcel D1 (Decision Mathematics 1) 2006 June

52 48 50 45 64 47 53 The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each completed pass. [4]

1. Define the term 'alternating path'. [2]
2. \includegraphics{figure_1} The bipartite graph in Figure 1 shows the films that six customers wish to hire this Saturday evening. The shop has only one copy of each film. The bold lines indicate an initial matching. Starting from this initial matching use the maximum matching algorithm twice to obtain a complete matching. You should clearly state the alternating paths you use. [5]

\includegraphics{figure_2} Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.

1. Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
2. State the length of the minimum route. [The total weight of the network is 394 km.] [1]

It is now permitted to start and finish the inspection at two distinct vertices.

1. State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]

1. Explain what is meant by the term 'path'. [2]

\includegraphics{figure_3} Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to I. Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. [6]
2. Explain how you determined the shortest path from your labelling. [2]

Mary wants to visit a theme park at E.

1. Find a path of minimal length that goes from A to I via E and state its length. [2]

\includegraphics{figure_4} An engineering project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest time.

1. Calculate the early time and late time for each event. Write these in boxes in Diagram 1 in the answer book. [4]
2. State the critical activities. [1]
3. Find the total float on activities D and F. You must show your working. [3]
4. On the grid in the answer book, draw a cascade (Gantt) chart for this project. [4]

The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,

1. which activities must be happening on each of these two days? [3]

The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

\includegraphics{figure_5} Figure 5 shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from S to T. Two cuts \(C_1\) and \(C_2\) are shown on Figure 5.

1. Write down the capacity of each of the two cuts and the value of the initial flow. [3]
2. Complete the initialisation of the labelling procedure on Diagram 1 by entering values along arcs AC, CD, DE and DT. [2]
3. Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow. [5]
4. Show your maximal flow pattern on Diagram 2. [2]
5. Prove that your flow is maximal. [2]