General Mathematics · Unit 4 · Topic 5

Networks and decision mathematics 2

Find the capacity of a cut, the minimum cut and the maximum flow through a flow network, then allocate people to tasks at the least cost or the greatest benefit by inspection and with the Hungarian algorithm.

  • 7 lessons
  • 1 h 56 min of lessons
  • 10 worked examples
  • 11 hours in the syllabus
0 of 7

Start here

Flow networks: sources, sinks and capacities

Lesson 1 of 7 · 14 min

Start the topic

Lessons

7
  1. Flow networks: sources, sinks and capacities (up next)

    Read a flow network — its source, sink and edge capacities — find the most that can flow along a single path, and use the rule that flow in equals flow out at every junction.

  2. Cuts and their capacity

    Recognise a cut in a flow network, name its source and sink sides, and find its capacity by adding only the edges that cross from the source side to the sink side.

  3. Minimum cut and maximum flow

    List every cut of a small flow network systematically, find the minimum cut, and use the maximum flow–minimum cut theorem to state the maximum flow, confirming it with a flow that reaches it.

  4. Solving practical flow problems

    Model roads, pipes and paths as flow networks, find the maximum flow, turn it into times and totals, and decide which upgrade would actually increase the flow.

  5. Allocation problems and bipartite graphs

    Represent an allocation problem as a bipartite graph and as a table or matrix, then find the best allocation of a small problem by inspection.

  6. The Hungarian algorithm for a minimum

    Use row reduction, column reduction, covering lines and the adjustment step to find the allocation with the smallest total cost or time for a 3 × 3 to 5 × 5 problem.

  7. Maximum assignments and more than one optimum

    Find the allocation with the largest total by converting a maximum problem into a minimum one, and find every optimal assignment when there is more than one.

  8. Topic quiz

    Ten questions across the topic, from foundation to complex unfamiliar. Your results feed your mastery.

About this topic

Water through pipes, cars along roads, data through cables: each travels through a network whose links can only carry so much. A flow network records those limits on its edges, and asks a practical question — what is the most that can get from the start to the finish? You will answer it with cuts, lines that split the network in two, and a remarkable fact: the maximum flow equals the capacity of the smallest cut.

The second half of the topic is about allocation. Four workers, four jobs, and a table of how long each worker takes on each job: who should do what? For three people you can check every possibility by hand. For five there are 120 possibilities, so you will learn the Hungarian algorithm, which finds the best allocation in a handful of tidy steps — for the smallest total cost or time, and for the largest total profit or score.

Both halves reward careful, visible working. Name the edges in every cut you add up, and show each table as the algorithm changes it.

Before you start

Builds on Graphs and networks and Networks and decision mathematics 1.

  • Graph vocabulary from Graphs and networks: vertex, edge, directed graph (digraph), weighted graph, network and bipartite graph.
  • Reading a matrix by rows and columns, and the idea of a square matrix (Unit 2, Matrices).
  • Adding and subtracting whole numbers quickly and accurately — most marks here are lost to arithmetic slips.

What QCAA says you need to know7 dot points

Flow networks

4 hours

Assigning order and the Hungarian algorithm

7 hours

Subject matter from the General Mathematics General senior syllabus 2025 v1.3 (opens in a new tab), CC BY 4.0 © State of Queensland (QCAA).

The focus areas you can practise on their own. Each one maps to dot points above.

  • Reading flow networks

    Source and sink, edge capacities, the flow along a path (limited by its smallest capacity) and flow in equals flow out at every other vertex.

    Practise
  • Identifying cuts

    Decide whether a line or a split of the vertices is a cut, and name its source side, sink side and the edges it crosses.

    Practise
  • Capacity of a cut

    Add the capacities of the edges crossing from the source side to the sink side, leaving out any edge that points back.

    Practise
  • Minimum cut and maximum flow

    Check every cut, find the minimum cut, and use maximum flow = minimum cut, confirming with a flow that achieves it.

    Practise
  • Flow network problems

    Model pipes, roads and cables as flow networks; work out times, bottlenecks and the effect of upgrading an edge.

    Practise
  • Bipartite graphs and allocation tables

    Represent an allocation problem as a bipartite graph and as a table or matrix, and read possible assignments from either.

    Practise
  • Assignment by inspection

    For small problems, list or reason through the possible allocations to find the minimum or maximum total.

    Practise
  • Steps of the Hungarian algorithm

    Row and column reduction, covering the zeros with the fewest lines, and the adjustment step.

    Practise
  • Minimum assignment (Hungarian)

    Run the Hungarian algorithm to the end, read the optimal assignment(s) from the zeros and total them from the original table.

    Practise
  • Maximum assignment

    Turn a maximum problem into a minimum one by subtracting every entry from the largest, then apply the Hungarian algorithm.

    Practise

Worked examples10

All 10

Common mistakes

Counting edges that cross a cut backwards

Only edges pointing from the source side to the sink side add to a cut's capacity. An edge crossing the cut towards the source side carries nothing towards the sink, so it counts as 0 — never subtract it and never add it.

Calling any line a cut

A cut must separate the source from the sink: after removing the edges it crosses, no path from source to sink is left. A line that only fences off one middle vertex is not a cut.

Taking the biggest cut, or the source's total, as the maximum flow

The maximum flow is the smallest cut capacity. The edges leaving the source might hold 25, but if some other cut holds only 22, no more than 22 can get through.

Missing a cut

With kk middle vertices there are 2k2^k cuts. List them systematically (none on the source side, then one, then two, …) so none is skipped — the one you skip might be the minimum.

Reading the total from the reduced matrix

The zeros in the final matrix show who does what. The total cost comes from the original table.

Drawing more lines than needed

The test is the fewest lines that cover every zero. Covering four zeros with four lines when three would do makes you stop too early with an assignment that does not exist.

Getting the adjustment step backwards

Subtract the smallest uncovered number from the uncovered entries only, and add it where two lines cross. Entries under exactly one line do not change.

Running the algorithm for a minimum on a maximum problem

For profits, scores or sales you want the largest total. First subtract every entry from the largest entry in the table, then minimise.

Giving one optimal assignment as the only answer

If the zeros allow more than one complete assignment, each has the same optimal total. When a question asks for the assignment/s, give all of them.

Exam tips

  1. Name every edge in a cut and show the sum, for example "C2C_2: SA+AB+BT=12+4+8=24SA + AB + BT = 12 + 4 + 8 = 24", and say which edges you left out because they point back.

  2. For maximum flow, list all the cuts (at most 8 in an exam question), circle the smallest, then state "maximum flow = minimum cut = …" with units.

  3. Back up a maximum flow by showing a flow that reaches it: flows along a few paths that respect every capacity and add to the minimum cut.

  4. Write out every matrix of the Hungarian algorithm: after row reduction, after column reduction, with the covering lines marked, and after each adjustment.

  5. State the number of lines and compare it with nn: "3 lines < 4, so adjust" or "4 lines = 4, so an optimal assignment exists".

  6. Finish an assignment question with a clear allocation (for example "Ana – Job 4, Ben – Job 2, …") and the total taken from the original table, with units.

  7. For a maximum problem, say what you did and why: "subtract each entry from the largest, 24, so the Hungarian algorithm for a minimum finds the maximum."

  8. Check your answer is reasonable: a minimum total can't be less than the sum of the row minimums, and a maximum flow can't exceed the total leaving the source.

Where this shows up

  • Water and gas utilities size their pipes using flow networks; the minimum cut shows which pipes limit supply, and so which ones are worth upgrading.

  • Emergency planners model evacuation routes as flow networks with capacities in vehicles per minute, then estimate how long it would take to clear a town.

  • Internet and phone providers treat cables and links as edges with bandwidths; the maximum flow is the most data the network can carry between two points.

  • Sports coaches assign swimmers to the legs of a medley relay to give the smallest total time — a 4×44 \times 4 assignment problem.

  • Delivery companies, hospitals and councils allocate drivers to routes, nurses to wards and crews to jobs, minimising time or cost.

  • Businesses assign salespeople to regions or staff to shifts to maximise total sales or satisfaction — a maximum assignment problem.

Save your progress with a free account