2 P62678A 1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G. A B C D E F G A – 24 – 22 35 – – B 24 – 25 27 – – – C – 25 – 33 31 36 26 D 22 27 33 – – 42 – E 35 – 31 – – 37 29 F – – 36 42 37 – 40 G – – 26 – 29 40 – (a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2) (b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3) (c) State the weight of the minimum spanning tree. (1) (Total for Question 1 is 6 marks) 3 P62678A Turn over 2. A(6) B(7) C(5) G(4) H(3) D(4) E(5) I(4) F(3) K(5) L(6) J(6) Figure 1 The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets. (a) Explain why each of the dummy activities is required. (2) (b) Complete the table in the answer book to show the immediately preceding activities for each activity. (2) (c) (i) Complete Diagram 1 in the answer book to show the early event times and the late event times. (ii) State the minimum completion time for the project. (iii) State the critical activities. (6) Each activity requires one worker. Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption. (d) On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. (3) (e) Determine whether or not the project can be completed in the minimum possible time using fewer workers than the number indicated by the resource histogram in (d). You must justify your answer with reference to the resource histogram and the completed Diagram 1. (2) (Total for Question 2 is 15 marks) 4 P62678A 3. A B C D E 1 7 8 3 6 4 10 1 Figure 2 Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages. (a) Set up initial time and route matrices. (2) The matrices after two iterations of Floyd’s algorithm are shown below. Time matrix Route matrix A B C D E A – 8 4 7 18 B 8 – 3 15 10 C 4 3 – 11 6 D 7 15 1 – 1 E 18 10 6 1 – A B C D E A A B C D B B A B C A E C A B C A E D A A C D E E B B C D E (b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4) The final time matrix after completion of Floyd’s algorithm is shown below. Final time matrix A B C D E A – 7 4 7 8 B 7 – 3 10 9 C 4 3 – 7 6 D 5 4 1 – 1 E 6 5 2 1 – 5 P62678A Turn over (c) (i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times. (ii) Find the time taken for this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (3) (Total for Question 3 is 9 marks) 6 P62678A 4. y O 7 – 6 – 5 – 4 – 3 – 2 – 1 – 1 2 3 4 5 x 2y = 5x 6x + 5y = 30 R y = x + 1 – – – – – – – Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y, where R is the feasible region. (a) Write down the inequalities that define R. (2) The objective is to maximise P, where P = 3x + y (b) Obtain the exact value of P at each of the three vertices of R and hence find the optimal vertex, V. (4) The objective is changed to maximise Q, where Q = 3x + ay. Given that a is a constant and the optimal vertex is still V, (c) find the range of possible values of a. (4) (Total for Question 4 is 10 marks)