| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Easy -1.2 This is a routine network flows question testing basic definitions (source, sink, capacity) and conservation of flow at vertices. Parts (a)-(c) are direct reading from the diagram, (d) involves simple arithmetic using flow conservation, (e) sums flows, and (f) applies the cut definition. All are standard textbook exercises requiring recall and straightforward calculation with no problem-solving insight needed. |
| Spec | 7.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 tree7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Capacity of \(EF = 19\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Source vertex \(= A\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Sink vertex \(= G\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x = 20\) | B1 | Using flow conservation |
| \(y = 15\) | B1 | |
| \(z = 42\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial flow \(= 30\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Cut value \(= 18 + 20 + 19 + 14 = 71\) | B1 | Sum of capacities of forward edges only |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Capacity of $EF = 19$ | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Source vertex $= A$ | B1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Sink vertex $= G$ | B1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $x = 20$ | B1 | Using flow conservation |
| $y = 15$ | B1 | |
| $z = 42$ | B1 | |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial flow $= 30$ | B1 | |
## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| Cut value $= 18 + 20 + 19 + 14 = 71$ | B1 | Sum of capacities of forward edges only |
---2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second.\\
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}
\begin{enumerate}[label=(\alph*)]
\item Write down the capacity of edge $E F$.
\item State the source vertex.
\item State the sink vertex.
\item Find the values of $x , y$ and $z$.
\item Find the value of the initial flow.
\item Find the value of a cut through the edges $E B , E C , E D , E F$ and $E G$.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q2 [8]}}