Question 5 - A-Level Maths

OCR D2 2011 June — Question 5 19 marks

Exam Board	OCR
Module	D2 (Decision Mathematics 2)
Year	2011
Session	June
Marks	19
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Explain capacity/flow constraints
Difficulty	Standard +0.3 This is a standard textbook application of max-flow min-cut theorem with routine procedures (calculating cut capacity, showing flows, finding augmenting paths). Part (ii) requires basic logical reasoning about flow conservation, but all parts follow algorithmic methods taught directly in D2 with no novel problem-solving required. Slightly easier than average due to its procedural nature.
Spec	7.02q Adjacency matrix: and weighted matrix representation 7.04f Network problems: choosing appropriate algorithm

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}

Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
Show the excess capacities and potential backflows when there is no flow.
Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
Show the maximum flow and explain how you know that this flow is maximal.

Show LaTeX source

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from $S$ to $T$. The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem.\\
\includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}\\
(i) Calculate the capacity of the cut that separates $\{ S , A , C , G \}$ from $\{ B , D , E , F , T \}$.\\
(ii) Explain why neither arc $S A$ nor arc $E T$ can be full to capacity. Also explain why the arcs $A C$ and $B C$ cannot simultaneously be full to capacity.\\
(iii) Show a flow of 3300 people per hour, and find a cut of capacity 3300 .

The direction of flow in $B C$ is reversed.\\
(iv) Show the excess capacities and potential backflows when there is no flow.\\
(v) Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along $S B E T$.\\
(vi) Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from $S$ to $T$.\\
(vii) Show the maximum flow and explain how you know that this flow is maximal.

\hfill \mbox{\textit{OCR D2 2011 Q5 [19]}}

This paper (6 questions)

View full paper

Q1 6 Q2 12 Q3 12 Q4 14 Q5 19 Q6 9