Further Maths Flows in networks Practice Questions

Free Further Maths Flows in networks practice questions with full step-by-step worked solutions. Covers flows, max-flow-min-cut, networks, value-of-a-flow. Practise exam-style problems and check your method.

flowsmax-flow-min-cutnetworksvalue-of-a-flowcutscapacity-of-a-cut
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:4, S→B:3, A→B:2, A→T:3, B→T:5}\{S\to A:4,\ S\to B:3,\ A\to B:2,\ A\to T:3,\ B\to T:5\}. Find the value of the maximum flow from SS to TT.
Show worked solution

Worked solution

  1. Write down the network as data

    N: {S→A:4, S→B:3, A→B:2, A→T:3, B→T:5}N:\ \{S\to A:4,\ S\to B:3,\ A\to B:2,\ A\to T:3,\ B\to T:5\}

    The source, the sink, the arcs and their capacities describe the whole network.

  2. Add the capacities of the arcs leaving SS

    ∑vc(S,v)=4+3=7\sum_{v}c(S,v)=4+3=7

    These are the arcs pointing away from SS.

  3. State the value of the maximum flow

    max⁡val⁡(f)=7\max\operatorname{val}(f)=7

    No larger flow can be sent from the source to the sink.

Answer
max⁡val⁡(f)=7\max\operatorname{val}(f)=7
Question 2
2 markseasy
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:4, S→B:3, A→B:2, A→T:3, B→T:5}\{S\to A:4,\ S\to B:3,\ A\to B:2,\ A\to T:3,\ B\to T:5\}. By the maximum-flow minimum-cut theorem, which of the following is the value of the maximum flow from SS to TT?
Show worked solution

Worked solution

  1. Write down the network as data

    N: {S→A:4, S→B:3, A→B:2, A→T:3, B→T:5}N:\ \{S\to A:4,\ S\to B:3,\ A\to B:2,\ A\to T:3,\ B\to T:5\}

    The source, the sink, the arcs and their capacities describe the whole network.

  2. Add the capacities of the arcs leaving SS

    ∑vc(S,v)=4+3=7\sum_{v}c(S,v)=4+3=7

    These are the arcs pointing away from SS.

  3. Select the value of the maximum flow

    max⁡val⁡(f)=7\max\operatorname{val}(f)=7

    This value is achieved and cannot be exceeded.

Answer
max⁡val⁡(f)=7\max\operatorname{val}(f)=7
Question 3
4 marksintermediate
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:3, S→B:6, A→B:4, A→C:5, B→C:2, B→D:5, C→T:4, D→T:6, C→D:2}\{S\to A:3,\ S\to B:6,\ A\to B:4,\ A\to C:5,\ B\to C:2,\ B\to D:5,\ C\to T:4,\ D\to T:6,\ C\to D:2\}. The flow ff assigns arc values {S→A:3, S→B:5, A→B:0, A→C:3, B→C:0, B→D:5, C→T:3, D→T:5, C→D:0}\{S\to A:3,\ S\to B:5,\ A\to B:0,\ A\to C:3,\ B\to C:0,\ B\to D:5,\ C\to T:3,\ D\to T:5,\ C\to D:0\}. Which of the following is a flow-augmenting path from SS to TT, together with the increase it gives?
Show worked solution

Worked solution

  1. Write down the network as data

    N: {S→A:3, S→B:6, A→B:4, A→C:5, B→C:2, B→D:5, C→T:4, D→T:6, C→D:2}N:\ \{S\to A:3,\ S\to B:6,\ A\to B:4,\ A\to C:5,\ B\to C:2,\ B\to D:5,\ C\to T:4,\ D\to T:6,\ C\to D:2\}

    The source, the sink, the arcs and their capacities describe the whole network.

  2. Write down the given flow

    f: {S→A:3, S→B:5, A→B:0, A→C:3, B→C:0, B→D:5, C→T:3, D→T:5, C→D:0}f:\ \{S\to A:3,\ S\to B:5,\ A\to B:0,\ A\to C:3,\ B\to C:0,\ B\to D:5,\ C\to T:3,\ D\to T:5,\ C\to D:0\}

    Each arc carries the amount of flow shown.

  3. Find the spare capacity on the forward arc S→BS\to B

    c(S,B)−f(S,B)=6−5=1c(S,B)-f(S,B)=6-5=1

    A forward arc can take up to its spare capacity.

  4. Find the spare capacity on the forward arc B→CB\to C

    c(B,C)−f(B,C)=2−0=2c(B,C)-f(B,C)=2-0=2

    A forward arc can take up to its spare capacity.

  5. Find the spare capacity on the forward arc C→DC\to D

    c(C,D)−f(C,D)=2−0=2c(C,D)-f(C,D)=2-0=2

    A forward arc can take up to its spare capacity.

  6. Find the spare capacity on the forward arc D→TD\to T

    c(D,T)−f(D,T)=6−5=1c(D,T)-f(D,T)=6-5=1

    A forward arc can take up to its spare capacity.

  7. Select the flow-augmenting path

    δ=1\delta=1

    Every arc on this path has spare capacity, so the flow can increase.

Answer
δ=1\delta=1
Question 4
6 markshard
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:3, S→B:6, A→B:4, A→C:5, B→C:2, B→D:5, C→T:4, D→T:6, C→D:2}\{S\to A:3,\ S\to B:6,\ A\to B:4,\ A\to C:5,\ B\to C:2,\ B\to D:5,\ C\to T:4,\ D\to T:6,\ C\to D:2\}. Which of the following is a minimum cut of NN, together with its capacity?
Show worked solution

Worked solution

  1. Write down the network as data

    N: {S→A:3, S→B:6, A→B:4, A→C:5, B→C:2, B→D:5, C→T:4, D→T:6, C→D:2}N:\ \{S\to A:3,\ S\to B:6,\ A\to B:4,\ A\to C:5,\ B\to C:2,\ B\to D:5,\ C\to T:4,\ D\to T:6,\ C\to D:2\}

    The source, the sink, the arcs and their capacities describe the whole network.

  2. Add the capacities of the arcs leaving SS

    ∑vc(S,v)=3+6=9\sum_{v}c(S,v)=3+6=9

    These are the arcs pointing away from SS.

  3. Identify the arcs crossing the cut from the source side

    S→A, S→BS\to A,\ S\to B

    Only arcs from the source side to the sink side are counted.

  4. Add the capacities of those arcs

    C=3+6=9C=3+6=9

    Arcs pointing back from the sink side are ignored.

  5. Confirm the flow reaches this cut value

    max⁡val⁡(f)=9\max\operatorname{val}(f)=9

    A cut whose capacity equals the maximum flow is a minimum cut.

  6. Recall the value of a flow

    val⁡(f)=∑vf(S,v)−∑vf(v,S)\operatorname{val}(f)=\sum_{v}f(S,v)-\sum_{v}f(v,S)

    The value of a flow is the net flow out of the source.

  7. Recall flow conservation at an intermediate vertex

    ∑uf(u,x)=∑wf(x,w)\sum_{u}f(u,x)=\sum_{w}f(x,w)

    At every vertex except the source and the sink, flow in equals flow out.

  8. Recall the capacity constraint on each arc

    0≤f(u,v)≤c(u,v)0\le f(u,v)\le c(u,v)

    No arc may carry more flow than its capacity.

  9. Recall the definition of a cut

    a cut splits the vertices into a source side and a sink side\text{a cut splits the vertices into a source side and a sink side}

    The source lies on one side of the cut and the sink on the other.

  10. Recall the capacity of a cut

    C=∑u∈S-side, v∈T-sidec(u,v)C=\sum_{u\in S\text{-side},\ v\in T\text{-side}}c(u,v)

    Only arcs crossing from the source side to the sink side are counted.

  11. Select the minimum cut

    min⁡C=9\min C=9

    Its capacity equals the maximum flow, which proves it is minimal.

Answer
min⁡C=9\min C=9
Question 5
9 markschallenging
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:5, S→B:6, A→C:4, A→D:3, B→D:5, C→T:6, D→T:4, B→C:2}\{S\to A:5,\ S\to B:6,\ A\to C:4,\ A\to D:3,\ B\to D:5,\ C\to T:6,\ D\to T:4,\ B\to C:2\}. The flow ff assigns arc values {S→A:4, S→B:4, A→C:4, A→D:0, B→D:4, C→T:4, D→T:4, B→C:0}\{S\to A:4,\ S\to B:4,\ A\to C:4,\ A\to D:0,\ B\to D:4,\ C\to T:4,\ D\to T:4,\ B\to C:0\}. Find the value of the flow ff.
Show worked solution

Worked solution

  1. Write down the network as data

    N: {S→A:5, S→B:6, A→C:4, A→D:3, B→D:5, C→T:6, D→T:4, B→C:2}N:\ \{S\to A:5,\ S\to B:6,\ A\to C:4,\ A\to D:3,\ B\to D:5,\ C\to T:6,\ D\to T:4,\ B\to C:2\}

    The source, the sink, the arcs and their capacities describe the whole network.

  2. Write down the given flow

    f: {S→A:4, S→B:4, A→C:4, A→D:0, B→D:4, C→T:4, D→T:4, B→C:0}f:\ \{S\to A:4,\ S\to B:4,\ A\to C:4,\ A\to D:0,\ B\to D:4,\ C\to T:4,\ D\to T:4,\ B\to C:0\}

    Each arc carries the amount of flow shown.

  3. Add the flow along the arcs leaving the source SS

    val⁡(f)=4+4=8\operatorname{val}(f)=4+4=8

    The value of a flow is the net flow out of the source.

  4. Recall the value of a flow

    val⁡(f)=∑vf(S,v)−∑vf(v,S)\operatorname{val}(f)=\sum_{v}f(S,v)-\sum_{v}f(v,S)

    The value of a flow is the net flow out of the source.

  5. Recall flow conservation at an intermediate vertex

    ∑uf(u,x)=∑wf(x,w)\sum_{u}f(u,x)=\sum_{w}f(x,w)

    At every vertex except the source and the sink, flow in equals flow out.

  6. Recall the capacity constraint on each arc

    0≤f(u,v)≤c(u,v)0\le f(u,v)\le c(u,v)

    No arc may carry more flow than its capacity.

  7. Recall the definition of a cut

    a cut splits the vertices into a source side and a sink side\text{a cut splits the vertices into a source side and a sink side}

    The source lies on one side of the cut and the sink on the other.

  8. Recall the capacity of a cut

    C=∑u∈S-side, v∈T-sidec(u,v)C=\sum_{u\in S\text{-side},\ v\in T\text{-side}}c(u,v)

    Only arcs crossing from the source side to the sink side are counted.

  9. Recall the maximum-flow minimum-cut theorem

    max⁡val⁡(f)=min⁡C\max\operatorname{val}(f)=\min C

    The value of a maximum flow equals the capacity of a minimum cut.

  10. Recall the weak-duality bound

    val⁡(f)≤C\operatorname{val}(f)\le C

    Every flow value is at most the capacity of every cut.

  11. Recall how a cut proves optimality

    val⁡(f)=C ⇒ f is maximal\operatorname{val}(f)=C\ \Rightarrow\ f\text{ is maximal}

    If a flow and a cut have the same size, neither can be improved.

  12. Recall a saturated arc

    f(u,v)=c(u,v)f(u,v)=c(u,v)

    A saturated arc is full to its capacity.

  13. Recall the spare capacity of an arc

    spare=c(u,v)−f(u,v)\text{spare}=c(u,v)-f(u,v)

    This is how much more flow the arc could still carry.

  14. Recall a flow-augmenting path

    a path from S to T with spare capacity throughout\text{a path from }S\text{ to }T\text{ with spare capacity throughout}

    Along such a path the value of the flow can be increased.

  15. Recall forward and backward arcs on an augmenting path

    forward: c−f,backward: f\text{forward: }c-f,\qquad \text{backward: }f

    Forward arcs use spare capacity; backward arcs release existing flow.

  16. State the value of the flow

    val⁡(f)=8\operatorname{val}(f)=8

    This is the net flow out of the source.

Answer
val⁡(f)=8\operatorname{val}(f)=8

Unlock 65 more Flows in networks questions

Create a free account to work through every Further Maths Flows in networks question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Flows in networks practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingGame theory