Question 5 - A-Level Maths

OCR Further Discrete 2018 September — Question 5 10 marks

Exam Board	OCR
Module	Further Discrete (Further Discrete)
Year	2018
Session	September
Marks	10
Topic	Minimum Spanning Trees
Type	Define tree terminology
Difficulty	Moderate -0.8 This is a straightforward Further Maths Decision question testing basic understanding of MST concepts. Parts (i)-(iii) require simple explanations about LP formulations and constraints, part (iv) is a standard textbook MST algorithm application on a small 6-vertex network, and part (v) asks students to verify the solution matches. The network is small enough that Kruskal's or Prim's algorithm can be applied mechanically with minimal complexity. While it's Further Maths content, it requires only routine application of standard algorithms without novel insight or challenging problem-solving.
Spec	7.02p Networks: weighted graphs, modelling connections 7.02q Adjacency matrix: and weighted matrix representation 7.04c Travelling salesman upper bound: nearest neighbour method

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables $\mathrm { AB } , \mathrm { AC } , \ldots$ correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
Explain what is ensured by the constraint $\mathrm { AB } + \mathrm { AC } \geqslant 1$. Julie claims that the solution to the problem will give the minimum spanning tree for the network.
Find the minimum spanning tree for the network.
- State the algorithm you have used.
- Show your method clearly.
- Draw the tree.
- State the total weight of the tree.
- Find the solution to the problem given at the start of the question.
- You do not need to use a formal method.
- Draw the arcs in the solution.
- State the minimum value of the objective function.
Kim has a different network, exactly one of the arcs in this network is a directed arc.
Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

Show LaTeX source

5 Consider the problem given below:

$$\begin{array} { l l } 
\text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\
\text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\
& \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\
& \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\
& \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1
\end{array}$$

(i) Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables $\mathrm { AB } , \mathrm { AC } , \ldots$ correspond to arcs in a network.

The weight on each arc is the coefficient of the corresponding variable in the objective function.\\
(ii) Draw the network on the vertices in the Printed Answer Booklet.

A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.\\
(iii) Explain what is ensured by the constraint $\mathrm { AB } + \mathrm { AC } \geqslant 1$.

Julie claims that the solution to the problem will give the minimum spanning tree for the network.\\
(iv) Find the minimum spanning tree for the network.

\begin{itemize}
  \item State the algorithm you have used.
  \item Show your method clearly.
  \item Draw the tree.
  \item State the total weight of the tree.\\
(v) Find the solution to the problem given at the start of the question.
  \item You do not need to use a formal method.
  \item Draw the arcs in the solution.
  \item State the minimum value of the objective function.
\end{itemize}

Kim has a different network, exactly one of the arcs in this network is a directed arc.\\
Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.\\
(vi) Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

\hfill \mbox{\textit{OCR Further Discrete 2018 Q5 [10]}}

This paper (7 questions)

View full paper

Q1 7 Q2 8 Q3 9 Q4 19 Q5 10 Q6 8 Q7 13