AQA D1 (Decision Mathematics 1) 2009 June

1

1. Draw a bipartite graph representing the following adjacency matrix.

   	1	2	3	4	5	6
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   B	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   E	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Initially, \(A\) is matched to \(3 , B\) is matched to \(4 , C\) is matched to 2 , and \(E\) is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.
   \begin{center} \begin{tabular}{|l|l|} \hline \multirow[t]{3}{*}{\begin{tabular}{l}

2
2
\end{tabular}} & \multirow{3}{*}{\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_699_1486_269_366} \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_508_1272_462_366} }
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline \end{tabular} \end{center}

3

1. 1. State the number of edges in a minimum spanning tree for a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree for a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The number on each edge represents the distance between a pair of adjacent vertices.
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-06_921_1710_717_150}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
      \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_38_118_440_159}
      \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_40_118_529_159}

4 The diagram opposite shows a network of roads on a housing estate. The number on each edge is the length, in metres, of the road. Joe is starting a kitchen-fitting business.

1. Joe delivers leaflets advertising his business. He walks along all of the roads at least once, starting and finishing at \(C\). Find the length of an optimal Chinese postman route for Joe.
2. Joe gets a job fitting a kitchen in a house at \(T\). Joe starts from \(C\) and wishes to drive to \(T\). Use Dijkstra's algorithm on the diagram opposite to find the minimum distance to drive from \(C\) to \(T\). State the corresponding route. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-08_1791_1705_916_155}
3. 
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-09_2395_1602_312_260}

5 Angelo is visiting six famous places in Palermo: \(A , B , C , D , E\) and \(F\). He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled. The table shows the times, in minutes, taken to travel between the six places.

1. Give an example of a Hamiltonian cycle in this context.
2. 1. Show that, if the nearest neighbour algorithm starting from \(F\) is used, the total travelling time for Angelo would be 95 minutes.
   2. Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
3. Angelo starts from \(F\) and visits \(E\) next. He also visits \(B\) before he visits \(D\). Find an improved upper bound for Angelo's total travelling time.
   
   \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}

6 Each day, a factory makes three types of widget: basic, standard and luxury. The widgets produced need three different components: type \(A\), type \(B\) and type \(C\). Basic widgets need 6 components of type \(A , 6\) components of type \(B\) and 12 components of type \(C\).
Standard widgets need 4 components of type \(A , 3\) components of type \(B\) and 18 components of type \(C\).
Luxury widgets need 2 components of type \(A , 9\) components of type \(B\) and 6 components of type \(C\).
Each day, there are 240 components of type \(A\) available, 300 of type \(B\) and 900 of type \(C\).
Each day, the factory must use at least twice as many components of type \(C\) as type \(B\).
Each day, the factory makes \(x\) basic widgets, \(y\) standard widgets and \(z\) luxury widgets.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find four inequalities in \(x , y\) and \(z\) that model the above constraints, simplifying each inequality.
2. Each day, the factory makes the maximum possible number of widgets. On a particular day, the factory must make the same number of luxury widgets as basic widgets.
   1. Show that your answers in part (a) become $$2 x + y \leqslant 60 , \quad 5 x + y \leqslant 100 , \quad x + y \leqslant 50 , \quad y \geqslant x$$
   2. Using the axes opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region.
   3. Find the total number of widgets made on that day.
   4. Find all possible combinations of the number of each type of widget made that correspond to this maximum number.

7

1. The diagram shows a graph with 16 vertices and 16 edges.
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_365_758}
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_365_1080}
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_689_758}
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_200_689_1082}
   1. On Figure 1 below, add the minimum number of edges to make a connected graph.
   2. On Figure 2 opposite, add the minimum number of edges to make the graph Hamiltonian.
   3. On Figure 3 opposite, add the minimum number of edges to make the graph Eulerian.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. The number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\). \section*{Figure 1} \section*{Connected Graph} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_195_200_2014_758}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_197_200_2012_1082}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_758}
      \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_1080}
      \end{figure} \section*{Figure 2} \section*{Hamiltonian Graph} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_218_536_511_753}
      \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_213_212_836_753}
      \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_215_214_836_1073}
3. (iii) \section*{Eulerian Graph} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_207_204_1356_758}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_211_206_1354_1078}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_206_209_1681_753}
   \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_200_202_1681_1080}