| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.5 This is a standard Decision Mathematics 2 question testing routine application of cut capacity calculations and max-flow min-cut theorem. Part (a) involves straightforward arithmetic of edge capacities across cuts (mostly given), stating the max-flow min-cut result, and drawing a feasible flow. Part (b) applies the flow augmentation algorithm mechanically. While multi-part with several marks, it requires only direct application of taught algorithms with no problem-solving insight or novel reasoning. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs7.04f Network problems: choosing appropriate algorithm |
| Cut | Value | |
| \(\{ S \}\) | \(\{ A , B , C , T \}\) | 30 |
| \(\{ S , A \}\) | \(\{ B , C , T \}\) | 29 |
| \(\{ S , B \}\) | \(\{ A , C , T \}\) | 36 |
| \(\{ S , C \}\) | \(\{ A , B , T \}\) | 33 |
| \(\{ S , A , B \}\) | \(\{ C , T \}\) | |
| \(\{ S , A , C \}\) | \(\{ B , T \}\) | |
| \(\{ S , B , C \}\) | \(\{ A , T \}\) | |
| \(\{ S , A , B , C \}\) | \(\{ T \}\) | 30 |
| Path |
| ||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut \(= 18 + 10 + 8 = 36\) | B1 | Must identify the three edges crossing the cut: \(SA=18\), \(BT=10\)(?), \(CT=8\) — edges going from S-side to T-side |
| Answer | Marks | Guidance |
|---|---|---|
| Cut | Value | Mark |
| \(\{S,A,B\}\), \(\{C,T\}\) | \(7+5+8+10 = 30\) ... 28 | B1 |
| \(\{S,A,C\}\), \(\{B,T\}\) | 33 | B1 |
| \(\{S,B,C\}\), \(\{A,T\}\) | 29 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Maximum flow \(= \mathbf{29}\) | B1 | |
| Because the minimum cut \(= 29\) (cut \(\{S,A\},\{B,C,T\}\)) | B1 | Max-flow min-cut theorem |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Valid flow diagram totalling 29 on each route, respecting capacities | B1 | Flows consistent with max flow of 29 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct potential increases/decreases shown on diagram | M1 | Using initial flow from (a)(iv) as starting point; \(SC\) now capacity 9, \(AT\) now capacity 16 |
| Flow augmenting path(s) identified with correct additional flow | A1A1 | e.g. \(S \to C \to T\) (+4); \(S \to A \to T\) (+4) |
| Correct modification of diagram | A1 | |
| Total additional flow stated | A1A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| New maximum flow \(= \mathbf{37}\) | B1 | |
| Correct flow values shown on diagram | B1B1 | All edges labelled correctly consistent with new max flow |
# Question 6:
## Part (a)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut $= 18 + 10 + 8 = 36$ | B1 | Must identify the three edges crossing the cut: $SA=18$, $BT=10$(?), $CT=8$ — edges going from S-side to T-side |
## Part (a)(ii):
| Cut | Value | Mark |
|-----|-------|------|
| $\{S,A,B\}$, $\{C,T\}$ | $7+5+8+10 = 30$ ... **28** | B1 |
| $\{S,A,C\}$, $\{B,T\}$ | **33** | B1 |
| $\{S,B,C\}$, $\{A,T\}$ | **29** | B1 |
## Part (a)(iii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Maximum flow $= \mathbf{29}$ | B1 | |
| Because the minimum cut $= 29$ (cut $\{S,A\},\{B,C,T\}$) | B1 | Max-flow min-cut theorem |
## Part (a)(iv):
| Answer | Mark | Guidance |
|--------|------|----------|
| Valid flow diagram totalling 29 on each route, respecting capacities | B1 | Flows consistent with max flow of 29 |
## Part (b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct potential increases/decreases shown on diagram | M1 | Using initial flow from (a)(iv) as starting point; $SC$ now capacity 9, $AT$ now capacity 16 |
| Flow augmenting path(s) identified with correct additional flow | A1A1 | e.g. $S \to C \to T$ (+4); $S \to A \to T$ (+4) |
| Correct modification of diagram | A1 | |
| Total additional flow stated | A1A1 | |
## Part (b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| New maximum flow $= \mathbf{37}$ | B1 | |
| Correct flow values shown on diagram | B1B1 | All edges labelled correctly consistent with new max flow |6
\begin{enumerate}[label=(\alph*)]
\item The network shows a flow from $S$ to $T$ along a system of pipes, with the capacity in litres per second indicated on each edge.\\
\includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-14_510_936_411_552}
\begin{enumerate}[label=(\roman*)]
\item Show that the value of the cut shown on the diagram is 36 .
\item The cut shown on the diagram can be represented as $\{ S , B \} , \{ A , C , T \}$.
Complete the table below to give the value of each of the 8 possible cuts.
\begin{center}
\begin{tabular}{ | l | l | c | }
\hline
\multicolumn{2}{|c|}{Cut} & Value \\
\hline
$\{ S \}$ & $\{ A , B , C , T \}$ & 30 \\
\hline
$\{ S , A \}$ & $\{ B , C , T \}$ & 29 \\
\hline
$\{ S , B \}$ & $\{ A , C , T \}$ & 36 \\
\hline
$\{ S , C \}$ & $\{ A , B , T \}$ & 33 \\
\hline
$\{ S , A , B \}$ & $\{ C , T \}$ & \\
\hline
$\{ S , A , C \}$ & $\{ B , T \}$ & \\
\hline
$\{ S , B , C \}$ & $\{ A , T \}$ & \\
\hline
$\{ S , A , B , C \}$ & $\{ T \}$ & 30 \\
\hline
\end{tabular}
\end{center}
\item State the value of the maximum flow through the network, giving a reason for your answer.
Maximum flow is $\_\_\_\_$ because $\_\_\_\_$
\item Indicate on the diagram below a possible flow along each edge corresponding to this maximum flow.\\
\includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_469_933_406_550}
\end{enumerate}\item The capacities along $S C$ and along $A T$ are each increased by 4 litres per second.
\begin{enumerate}[label=(\roman*)]
\item Using your values from part (a)(iv) as the initial flow, indicate potential increases and decreases on the diagram below and use the labelling procedure to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the diagram.\\
\includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_470_935_1315_260}
\begin{center}
\begin{tabular}{ | c | c | }
\hline
Path & \begin{tabular}{ c }
Additional \\
Flow \\
\end{tabular} \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
& \\
\hline
\end{tabular}
\end{center}
\item Use your results from part (b)(i) to illustrate the flow along each edge that gives this new maximum flow, and state the value of the new maximum flow.
New maximum flow is $\_\_\_\_$\\
\includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_474_933_2078_550}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2012 Q6 [16]}}