Hard Further Maths Flows in networks Questions

Challenging, exam-style Further Maths Flows in networks questions with worked solutions. Stretch yourself on the hardest flows, max-flow-min-cut, networks, min-cut problems.

flowsmax-flow-min-cutnetworksmin-cutvalue-of-a-flowsaturated-arcs
Further Maths34 questionsStep-by-step solutions
Question 1
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
Question 2
9 markschallenging
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:8, S→B:6, S→C:5, A→D:5, B→D:4, B→E:5, C→E:6, D→F:6, E→F:5, F→T:9, D→T:3}\{S\to A:8,\ S\to B:6,\ S\to C:5,\ A\to D:5,\ B\to D:4,\ B\to E:5,\ C\to E:6,\ D\to F:6,\ E\to F:5,\ F\to T:9,\ D\to T:3\}. 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:8, S→B:6, S→C:5, A→D:5, B→D:4, B→E:5, C→E:6, D→F:6, E→F:5, F→T:9, D→T:3}N:\ \{S\to A:8,\ S\to B:6,\ S\to C:5,\ A\to D:5,\ B\to D:4,\ B\to E:5,\ C\to E:6,\ D\to F:6,\ E\to F:5,\ F\to T:9,\ D\to T:3\}

    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)=8+6+5=19\sum_{v}c(S,v)=8+6+5=19

    These are the arcs pointing away from SS.

  3. Add the capacities of the arcs entering TT

    ∑uc(u,T)=9+3=12\sum_{u}c(u,T)=9+3=12

    These are the arcs pointing towards TT.

  4. Quote the maximum-flow minimum-cut theorem

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

    The maximum flow equals the capacity of a minimum cut.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. Recall the weak-duality bound

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

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

  12. 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.

  13. Recall a saturated arc

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

    A saturated arc is full to its capacity.

  14. 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.

  15. Select the value of the maximum flow

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

    This value is achieved and cannot be exceeded.

Answer
max⁡val⁡(f)=12\max\operatorname{val}(f)=12
Question 3
9 markschallenging
The directed network NN has source SS and sink TT. The arcs and their capacities are {S→A:7, S→B:5, A→C:6, B→C:3, B→D:4, C→D:2, C→T:5, D→T:6}\{S\to A:7,\ S\to B:5,\ A\to C:6,\ B\to C:3,\ B\to D:4,\ C\to D:2,\ C\to T:5,\ D\to T:6\}. 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:7, S→B:5, A→C:6, B→C:3, B→D:4, C→D:2, C→T:5, D→T:6}N:\ \{S\to A:7,\ S\to B:5,\ A\to C:6,\ B\to C:3,\ B\to D:4,\ C\to D:2,\ C\to T:5,\ D\to T:6\}

    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)=7+5=12\sum_{v}c(S,v)=7+5=12

    These are the arcs pointing away from SS.

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

    S→B, A→CS\to B,\ A\to C

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

  4. Add the capacities of those arcs

    C=5+6=11C=5+6=11

    Arcs pointing back from the sink side are ignored.

  5. Confirm the flow reaches this cut value

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

    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. 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.

  12. Recall the weak-duality bound

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

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

  13. 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.

  14. Recall a saturated arc

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

    A saturated arc is full to its capacity.

  15. 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.

  16. 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.

  17. 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.

  18. Recall the increase given by the labelling procedure

    δ=min⁡(forward c−f, backward f)\delta=\min(\text{forward }c-f,\ \text{backward }f)

    The bottleneck of the path is the largest possible increase.

  19. Select the minimum cut

    min⁡C=11\min C=11

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

Answer
min⁡C=11\min C=11
Question 4
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\}. Find the capacity of the minimum cut of NN.
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. Add the capacities of the arcs leaving SS

    ∑vc(S,v)=5+6=11\sum_{v}c(S,v)=5+6=11

    These are the arcs pointing away from SS.

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

    A→C, D→T, B→CA\to C,\ D\to T,\ B\to C

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

  4. Add the capacities of those arcs

    C=4+4+2=10C=4+4+2=10

    Arcs pointing back from the sink side are ignored.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. Recall the weak-duality bound

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

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

  12. 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.

  13. Recall a saturated arc

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

    A saturated arc is full to its capacity.

  14. 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.

  15. 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.

  16. 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.

  17. Recall the increase given by the labelling procedure

    δ=min⁡(forward c−f, backward f)\delta=\min(\text{forward }c-f,\ \text{backward }f)

    The bottleneck of the path is the largest possible increase.

  18. State the capacity of the minimum cut

    min⁡C=10\min C=10

    By the maximum-flow minimum-cut theorem this equals the maximum flow.

Answer
min⁡C=10\min C=10
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\}. 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: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. Add the capacities of the arcs leaving SS

    ∑vc(S,v)=5+6=11\sum_{v}c(S,v)=5+6=11

    These are the arcs pointing away from SS.

  3. Add the capacities of the arcs entering TT

    ∑uc(u,T)=6+4=10\sum_{u}c(u,T)=6+4=10

    These are the arcs pointing towards TT.

  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. Recall the increase given by the labelling procedure

    δ=min⁡(forward c−f, backward f)\delta=\min(\text{forward }c-f,\ \text{backward }f)

    The bottleneck of the path is the largest possible increase.

  17. State the value of the maximum flow

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

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

Answer
max⁡val⁡(f)=10\max\operatorname{val}(f)=10

Unlock 29 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

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingGame theory