Question 5 - A-Level Maths

OCR D2 2010 June — Question 5 15 marks

Exam Board	OCR
Module	D2 (Decision Mathematics 2)
Year	2010
Session	June
Marks	15
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Network Flows
Type	Explain capacity/flow constraints
Difficulty	Standard +0.3 This is a standard network flows question testing routine application of max-flow min-cut theorem, cut capacity calculations, and flow augmentation. While multi-part with several marks, each component follows textbook procedures without requiring novel insight—slightly easier than average due to the algorithmic nature of Decision Maths content.
Spec	7.04f Network problems: choosing appropriate algorithm

5 Answer this question on the insert provided. The network represents a system of irrigation channels along which water can flow. The weights on the arcs represent the maximum flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-05_597_1553_479_296}

Calculate the capacity of the cut that separates \(\{ S , B , C , E \}\) from \(\{ A , D , F , G , H , T \}\).
Explain why neither arc \(S C\) nor arc \(B C\) can be full to capacity. Explain why the arcs \(E F\) and \(E H\) cannot both be full to capacity. Hence find the maximum flow along arc \(H T\). When arc \(H T\) carries its maximum flow, what is the flow along arc \(H G\) ?
Show a flow of 58 litres per second on the diagram in the insert, and find a cut of capacity 58. The direction of flow in \(H G\) is reversed.
Use the diagram in the insert to show the excess capacities and potential backflows for your flow from part (iii) in this case.
Without augmenting the labels from part (iv), write down flow augmenting routes to enable an additional 2 litres per second to flow from \(S\) to \(T\).
Show your augmented flow on the diagram in the insert. Explain how you know that this flow is maximal.

Show mark scheme Show mark scheme source

Question 5:

Part (i)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
\(21 + 36 + 7 + 18 = 82\)	M1	Evidence of using the correct cut (e.g. \(21\ (\pm 23) + 36 + 7 + 18\) seen)
\(= 82\)	A1	[2]

Part (ii)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
At most 17 can leave \(C\) so there cannot be as much as 20 or 18 entering it	B1	\(17 <\) both 20 and 18 (NOT \(17 < 38\))
At most 17 can enter \(E\) so there cannot be \(7 + 18 = 25\) leaving it	B1	\(17 < 7 + 18\)
Maximum that can flow in arc \(HT\) is 33	B1	33
Flow along arc \(HG = 0\)	B1	0

Part (iii)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
A diagram showing a flow of 58 in which amount in equals amount out at each vertex, apart from \(S\) and \(T\); arcs \(CE\), \(FH\) and \(GT\) are saturated and other arc capacities are not exceeded	M1, A1	Assume that "blanks" mean 0 or full to capacity, provided consistent
Cut \(X = \{S, A, B, C, D, F, G\}\), \(Y = \{E, H, T\}\); or cut through \(GT\), \(GH\), \(FH\), \(EF\) and \(CE\)	B1	This cut presented in any form (accept it drawn on diagram)

Part (iv)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Substantially correct attempt in which excess capacities and potential backflows marked correctly on arcs \(CE\), \(FH\) and \(GT\)	M1	Assume that blanks mean 0; accept all directions swapped
Their excess capacities and potential backflows marked correctly on arcs out of \(S\) and arcs into \(T\) and on \(HG\)	A1	Check directions on \(HG\) carefully; if no flow in (iii), or ambiguous, then any valid flow \(> 0\) labelled correctly gets M1, but must also be a flow of 58 to get A1

Part (v)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Feasible route(s) written that send an additional 2 through system (or more on follow through)	M1	Routes must be written out properly e.g. route \(SBFGHT\) by 2
All route(s) valid with an additional 2 along \(GH\)	A1	[2]

Part (vi)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Their flow from part (iii) augmented by their routes in part (v)	M1	Follow through if possible
No more can flow across the cut \(X = \{S, C\}\), \(Y = \{A, B, D, E, F, G, H, T\}\)	A1	Any reasonable explanation

# Question 5:

## Part (i)

| Answer/Working | Mark | Guidance |
|---|---|---|
| $21 + 36 + 7 + 18 = 82$ | M1 | Evidence of using the correct cut (e.g. $21\ (\pm 23) + 36 + 7 + 18$ seen) |
| $= 82$ | A1 | [2] |

## Part (ii)

| Answer/Working | Mark | Guidance |
|---|---|---|
| At most 17 can leave $C$ so there cannot be as much as 20 or 18 entering it | B1 | $17 <$ both 20 and 18 (NOT $17 < 38$) |
| At most 17 can enter $E$ so there cannot be $7 + 18 = 25$ leaving it | B1 | $17 < 7 + 18$ | [2] |
| Maximum that can flow in arc $HT$ is 33 | B1 | 33 |
| Flow along arc $HG = 0$ | B1 | 0 | [2] |

## Part (iii)

| Answer/Working | Mark | Guidance |
|---|---|---|
| A diagram showing a flow of 58 in which amount in equals amount out at each vertex, apart from $S$ and $T$; arcs $CE$, $FH$ and $GT$ are saturated and other arc capacities are not exceeded | M1, A1 | Assume that "blanks" mean 0 or full to capacity, provided consistent |
| Cut $X = \{S, A, B, C, D, F, G\}$, $Y = \{E, H, T\}$; or cut through $GT$, $GH$, $FH$, $EF$ and $CE$ | B1 | This cut presented in any form (accept it drawn on diagram) | [3] |

## Part (iv)

| Answer/Working | Mark | Guidance |
|---|---|---|
| Substantially correct attempt in which excess capacities and potential backflows marked correctly on arcs $CE$, $FH$ and $GT$ | M1 | Assume that blanks mean 0; accept all directions swapped |
| Their excess capacities and potential backflows marked correctly on arcs out of $S$ and arcs into $T$ and on $HG$ | A1 | Check directions on $HG$ carefully; if no flow in (iii), or ambiguous, then any valid flow $> 0$ labelled correctly gets M1, but must also be a flow of 58 to get A1 | [2] |

## Part (v)

| Answer/Working | Mark | Guidance |
|---|---|---|
| Feasible route(s) written that send an additional 2 through system (or more on follow through) | M1 | Routes must be written out properly e.g. route $SBFGHT$ by 2 |
| All route(s) valid with an additional 2 along $GH$ | A1 | [2] |

## Part (vi)

| Answer/Working | Mark | Guidance |
|---|---|---|
| Their flow from part (iii) augmented by their routes in part (v) | M1 | Follow through if possible |
| No more can flow across the cut $X = \{S, C\}$, $Y = \{A, B, D, E, F, G, H, T\}$ | A1 | Any reasonable explanation | [2] |

---

Show LaTeX source

5 Answer this question on the insert provided.
The network represents a system of irrigation channels along which water can flow. The weights on the arcs represent the maximum flow in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-05_597_1553_479_296}\\
(i) Calculate the capacity of the cut that separates $\{ S , B , C , E \}$ from $\{ A , D , F , G , H , T \}$.\\
(ii) Explain why neither arc $S C$ nor arc $B C$ can be full to capacity. Explain why the arcs $E F$ and $E H$ cannot both be full to capacity. Hence find the maximum flow along arc $H T$. When arc $H T$ carries its maximum flow, what is the flow along arc $H G$ ?\\
(iii) Show a flow of 58 litres per second on the diagram in the insert, and find a cut of capacity 58.

The direction of flow in $H G$ is reversed.\\
(iv) Use the diagram in the insert to show the excess capacities and potential backflows for your flow from part (iii) in this case.\\
(v) Without augmenting the labels from part (iv), write down flow augmenting routes to enable an additional 2 litres per second to flow from $S$ to $T$.\\
(vi) Show your augmented flow on the diagram in the insert. Explain how you know that this flow is maximal.

\hfill \mbox{\textit{OCR D2 2010 Q5 [15]}}

This paper (6 questions)

View full paper

Q1 6 Q2 10 Q3 11 Q4 15 Q5 15 Q6 15