AQA D2 2011 January — Question 6 11 marks

Exam BoardAQA
ModuleD2 (Decision Mathematics 2)
Year2011
SessionJanuary
Marks11
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNetwork Flows
TypeAdd supersource and/or supersink
DifficultyModerate -0.5 This is a standard textbook exercise on network flows requiring routine application of supersource/supersink addition and flow augmentation algorithm. While multi-part with several steps, each component follows a well-defined procedure taught in D2 with no novel problem-solving required, making it slightly easier than average.
Spec7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree
6 A retail company has warehouses at \(P , Q\) and \(R\), and goods are to be transported to retail outlets at \(Y\) and \(Z\). There are also retaining depots at \(U , V , W\) and \(X\). The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}
  1. On Figure 5 opposite, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
  2. On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
    1. On Figure 7, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
    2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
  4. Find a cut with value equal to the maximum flow. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
    \end{figure} \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Figure 6}
    RouteFlow
    SPUYT
    SRVWZT
    \end{table} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 7} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
    \end{figure}
Question 6:
Part (a):
AnswerMarks Guidance
Super-source \(S\) connected to \(P\), \(Q\), \(R\) with capacities \(\infty\) (or sufficiently large); super-sink \(T\) connected from \(Y\) and \(Z\) with capacities \(\infty\)B1 B1 One mark for sources, one for sinks
Part (b):
AnswerMarks
\(SPUYT\): bottleneck = \(\min(12,10,10)=10\), flow = 10B1
\(SRVWZT\): bottleneck = \(\min(9,9,5,10)... \) wait — edges: \(R\to W=9\), \(W\to Z=10\), \(W\to X=5\)... route \(SRVWZT\): \(R\to V=8\), \(V\to W=9\), \(W\to Z=10\); bottleneck \(=\min(8,9,10)=\) 8B1
Part (c)(i):
AnswerMarks
Potential increases/decreases labelled on edges of both routes with correct values based on flows 10 and 8M1 A1
Part (c)(ii):
AnswerMarks
Flow augmentation route(s) found; e.g. \(SQVXZT\) flow 7; total maximum flow = 25M1 A1 M1 A1
Part (d):
AnswerMarks
Cut: \(\{UY, XZ, WZ\}\) or equivalent cut of value 25B1 
# Question 6:

## Part (a):

Super-source $S$ connected to $P$, $Q$, $R$ with capacities $\infty$ (or sufficiently large); super-sink $T$ connected from $Y$ and $Z$ with capacities $\infty$ | B1 B1 | One mark for sources, one for sinks |

## Part (b):

$SPUYT$: bottleneck = $\min(12,10,10)=10$, flow = **10** | B1 |

$SRVWZT$: bottleneck = $\min(9,9,5,10)... $ wait — edges: $R\to W=9$, $W\to Z=10$, $W\to X=5$... route $SRVWZT$: $R\to V=8$, $V\to W=9$, $W\to Z=10$; bottleneck $=\min(8,9,10)=$ **8** | B1 |

## Part (c)(i):

Potential increases/decreases labelled on edges of both routes with correct values based on flows 10 and 8 | M1 A1 |

## Part (c)(ii):

Flow augmentation route(s) found; e.g. $SQVXZT$ flow 7; total maximum flow = **25** | M1 A1 M1 A1 |

## Part (d):

Cut: $\{UY, XZ, WZ\}$ or equivalent cut of value **25** | B1 |
6 A retail company has warehouses at $P , Q$ and $R$, and goods are to be transported to retail outlets at $Y$ and $Z$. There are also retaining depots at $U , V , W$ and $X$.

The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram.\\
\includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}
\begin{enumerate}[label=(\alph*)]
\item On Figure 5 opposite, add a super-source, $S$, and a super-sink, $T$, and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
\item On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
\item \begin{enumerate}[label=(\roman*)]
\item On Figure 7, add the vertices $S$ and $T$ and the edges connecting $S$ and $T$ to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
\item Use flow augmentation to find the maximum flow from $S$ to $T$. You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
\end{enumerate}\item Find a cut with value equal to the maximum flow.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 5}
  \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
\end{center}
\end{figure}

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\begin{tabular}{ | l | l | }
\hline
\multicolumn{1}{|c|}{Route} & Flow \\
\hline
SPUYT &  \\
\hline
SRVWZT &  \\
\hline
 &  \\
\hline
 &  \\
\hline
 &  \\
\hline
 &  \\
\hline
 &  \\
\hline
 &  \\
\hline
 &  \\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 7}
  \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
\end{center}
\end{figure}
\end{enumerate}

\hfill \mbox{\textit{AQA D2 2011 Q6 [11]}}
This paper (6 questions)
View full paper
Q1 14 Q2 13 Q3 13 Q4 15 Q5 9 Q6 11