3 (i) Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 .

A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.\\
A simply connected graph is one that is both simple and connected.\\
(ii) Explain why there is no simply connected graph with exactly four vertices of orders $1,1,2$ and 4.\\
(iii) A connected graph has four vertices $A , B , C$ and $D$, in which $A , B$ and $C$ have order 2 and $D$ has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph.

A graph has three vertices, $A , B$ and $C$ of orders $a , b$ and $c$, respectively.\\
(iv) What restrictions on the values of $a , b$ and $c$ follow from the graph being
\begin{enumerate}[label=(\alph*)]
\item simple,
\item connected,
\item semi-Eulerian?
\begin{enumerate}[label=(\roman*)]
\item Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of $n$ numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
\item Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order.

$$\begin{array} { l l l l l l } 
3 & 10 & 8 & 2 & 6 & 11
\end{array}$$

You do not need to count the number of comparisons and the number of swaps that are used.

Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required.

$$\begin{array} { l l l l l l } 
3 & 10 & 8 & 2 & 6 & 11
\end{array}$$
\item Use the first-fit method to find a way to cut the pieces.
\item Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
\item Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make?

5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address.

The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
\begin{enumerate}[label=(\roman*)]
\item Since $a \leqslant 6$ it follows that $6 - a \geqslant 0$, and similarly for $b$ and $c$. Let $6 - a = x$ (so that $a$ is replaced by $6 - x ) , 8 - b = y$ and $10 - c = z$ to show that the problem can be expressed as

$$\begin{array} { l l } 
\text { Maximise } & 2 x - 4 y + 5 z , \\
\text { subject to } & 3 x + 2 y - z \leqslant 14 , \\
& 2 x - 4 z \leqslant 7 , \\
& - 4 x + y \leqslant 4 , \\
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 .
\end{array}$$
\item Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of $a , b$ and $c$ after two iterations. Find the value of the objective for the original problem at this stage.\\[0pt]
[10]
\end{enumerate}
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{OCR D1 2011 Q3 [8]}}