Flows in networks Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Flows in networks questions. See exactly how to solve problems on flows, max-flow-min-cut, networks, value-of-a-flow.

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.

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\}. The flow ff assigns arc values {S→A:3, S→B:3, A→B:0, A→T:3, B→T:3}\{S\to A:3,\ S\to B:3,\ A\to B:0,\ A\to T:3,\ B\to T:3\}. Find the value of the flow ff.

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. Write down the given flow

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

    Each arc carries the amount of flow shown.

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

    val⁡(f)=3+3=6\operatorname{val}(f)=3+3=6

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

  4. State the value of the flow

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

    This is the net flow out of the source.

Answer
val⁡(f)=6\operatorname{val}(f)=6
Question 3
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\}. Consider the cut that partitions the vertices into {A,S}\{A,S\} and {B,T}\{B,T\}. Find the capacity of this cut.

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. Identify the arcs crossing the cut from the source side

    S→B, A→B, A→TS\to B,\ A\to B,\ A\to T

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

  3. State the capacity of the cut

    C=8C=8

    The capacity of a cut is the total capacity of its forward-crossing arcs.

Answer
C=8C=8
Question 4
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 total capacity of the arcs leaving the source SS.

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 total capacity out of the source

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

    This is the capacity of the cut that isolates the source.

Answer
∑vc(S,v)=7\sum_{v}c(S,v)=7
Question 5
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 total capacity of the arcs entering the sink TT.

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 entering TT

    ∑uc(u,T)=3+5=8\sum_{u}c(u,T)=3+5=8

    These are the arcs pointing towards TT.

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

  4. State the total capacity into the sink

    ∑uc(u,T)=8\sum_{u}c(u,T)=8

    This is the capacity of the cut that isolates the sink.

Answer
∑uc(u,T)=8\sum_{u}c(u,T)=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 QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingGame theory