Edexcel FD1 AS (Further Decision 1 AS) 2019 June

1. Draw the graph \(K_5\) [1]
2. 1. In the context of graph theory explain what is meant by 'semi-Eulerian'.
   2. Draw two semi-Eulerian subgraphs of \(K_5\), each having five vertices but with a different number of edges. [3]
3. Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. [2]

The following algorithm produces a numerical approximation for the integral $$I = \int_A^B x^4 \, 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 + A\(^4\) + B\(^4\)
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 × E\(^4\)
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,

1. 1. complete the table in the answer book to show the results obtained at each step of the algorithm.
   2. State the final output. [4]
2. 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]

1. 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.

1. Explain why activity B cannot be critical. [1]
2. State which other activities are not critical. [1]

\includegraphics{figure_1} **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.

1. 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.

1. State the arcs that are traversed twice. [1]
2. State the number of times that vertex C appears in the inspection route. [1]
3. Determine the length of the inspection route. [1]

Ben is a wedding planner. He needs to order flowers for the weddings that are taking place next month. The three types of flower he needs to order are roses, hydrangeas and peonies. Based on his experience, Ben forms the following constraints on the number of each type of flower he will need to order. • At least three-fifths of all the flowers must be roses. • For every 2 hydrangeas there must be at most 3 peonies. • The total number of flowers must be exactly 1000 The cost of each rose is £1, the cost of each hydrangea is £5 and the cost of each peony is £4 Ben wants to minimise the cost of the flowers. Let \(x\) represent the number of roses, let \(y\) represent the number of hydrangeas and let \(z\) represent the number of peonies that he will order.

1. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. [7]

Ben decides to order the minimum number of roses that satisfy his constraints.

1. 1. Calculate the number of each type of flower that he will order to minimise the cost of the flowers.
   2. Calculate the corresponding total cost of this order. [3]