P61639A 2 1. (a) Draw the graph K5 (1) (b) (i) In the context of graph theory explain what is meant by ‘semi-Eulerian’. (ii) Draw two semi-Eulerian subgraphs of K5, each having five vertices but with a different number of edges. (3) (c) Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. (2) (Total for Question 1 is 6 marks) 2. The following algorithm produces a numerical approximation for the integral I = A B∫ x4 dx Step 1 Start Step 2 Input the values of A, B and N Step 3 Let H = (B – A) / N Step 4 Let C = H / 2 Step 5 Let D = 0 Step 6 Let D = D + A4 + B4 Step 7 Let E = A Step 8 Let E = E + H Step 9 If E = B go to Step 12 Step 10 Let D = D + 2 × E4 Step 11 Go to Step 8 Step 12 Let F = C × D Step 13 Output F Step 14 Stop For the case when A = 1, B = 3 and N = 4, (a) (i) complete the table in the answer book to show the results obtained at each step of the algorithm. (ii) State the final output. (4) (b) Calculate, to 3 significant figures, the percentage error between the exact value of I and the value obtained from using the approximation to I in this case. (3) (Total for Question 2 is 7 marks) P61639A 3 Turn over 3. Activity Immediately preceding activities A - B - C A D A E A F B, C G B, C H D I D, E, F, G J D, E, F, G K G (a) Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain the minimum number of dummies. (5) Every activity shown in the precedence table has the same duration. (b) Explain why activity B cannot be critical. (1) (c) State which other activities are not critical. (1) (Total for Question 3 is 7 marks) P61639A 4 4. B A C D E F G H 10 17 12 16 13 25 3x + y x + y 9 5 9 7 7 3 2 Figure 1 [The total weight of the network is 135 + 4x + 2y] The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of x and y, where x and y are positive constants and 7 x + y 20 There are three paths from A to H that have the same minimum length. (a) Use Dijkstra’s algorithm to find x and y. (7) An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length. (b) State the arcs that are traversed twice. (1) (c) State the number of times that vertex C appears in the inspection route. (1) (d) Determine the length of the inspection route. (1) (Total for Question 4 is 10 marks)