Flows in Networks Topic Review summary

Key learning points

• A cut partitions vertices into sets containing source and sink; capacity is sum of forward edge capacities across the cut.
• Max-flow min-cut: maximum flow equals capacity of a minimum cut.
• Augmenting paths increase flow; residual capacities matter.
• Vertex capacities can be modelled by splitting vertices.
• State flow on each edge and the total when asked.

Worked example 1 — Min cut

Why does a cut upper-bound the flow?

Working

Hence max flow ≤ every cut capacity.

Worked example 2 — Augment

Residual capacity on an edge with cap 10 and flow 4?

Working

You can push 6 more forward.

Worked example 3 — Practice point 1

Apply this idea from the Topic Review: A cut partitions vertices into sets containing source and sink; capacity is sum of forward edge capacities across the cut.

Working

Attempt without notes, then check the answers PDF.

Worked example 4 — Practice point 2

Apply this idea from the Topic Review: Max-flow min-cut: maximum flow equals capacity of a minimum cut.

Working

Attempt without notes, then check the answers PDF.

Scaffolded Learning Sheet and answers (PDFs)

This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.