Edexcel D1 (Decision Mathematics 1) 2002 November

1. Figure 1
   \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}

A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).

1. Complete this Hamiltonian cycle.
2. Hence use the planarity algorithm to determine if the graph is planar.

2. The precedence table for activities involved in manufacturing a toy is shown below.

1. Draw an activity network, using activity on arc, and exactly one dummy, to model the manufacturing process.
2. Explain briefly why it is necessary to use a dummy in this case.

3. At a water sports centre there are five new instructors. Ali (A), George ( \(G\) ), Jo ( \(J\) ), Lydia ( \(L\) ) and Nadia \(( N )\). They are to be matched to five sports, canoeing \(( C )\), scuba diving \(( D )\), surfing \(( F )\), sailing ( \(S\) ) and water skiing ( \(W\) ). The table indicates the sports each new instructor is qualified to teach. Initially, \(A , G , J\) and \(L\) are each matched to the first sport in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used. Given that on a particular day \(J\) must be matched to \(D\),
3. explain why it is no longer possible to find a complete matching.
   \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-4_720_1305_391_236} Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes \(A\), \(B , C , D , E , F , G\) and \(H\) represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe. Each pipe must be traversed at least once and the length of the inspection route must be minimised.

1. Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node \(C\). The inspection must still traverse each pipe at least once but may finish at any node.
2. Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
   (3)

5. \begin{figure}[h] \end{figure}

1. Use Dijkstra's algorithm to find the shortest route from \(S\) to \(T\) in Fig. 3. Show all necessary working in the boxes in the answer booklet. State your shortest route and its length.
2. Explain how you determined the shortest route from your labelling.
3. It is now necessary to go from \(S\) to \(T\) via \(H\). Obtain the shortest route and its length.

6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)

1. 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 complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
2. Determine the least number of bins needed.
3. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .

7. \begin{figure}[h] \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-6_525_1404_1233_345}
   \end{figure} Figure 5 shows a feasible flow through the same network.
2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
   (6)
4. Show the maximal flow on Diagram 2 and state its value.
5. Prove that your flow is maximal.

8. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
   (4) An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
   (2)