Skip to main content
MathidiaMathematics Academy
Graph theory and networks
Lesson 50 of 75
Review

Network flows

Objective. Find maximum flows and minimum cuts.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Network flow theory studies how much material can move from a source s to a sink t through a directed graph with edge capacities, where the maximum flow equals the minimum cut capacity (max-flow min-cut theorem) separating s from t. The Ford-Fulkerson method repeatedly finds augmenting paths with spare capacity in the residual graph and pushes flow along them until none remain. For example, a network with a single path s→a→t of capacities 5 and 3 has maximum flow 3, bottlenecked by the smaller edge. A minimum cut partitions the vertices into two sets containing s and t respectively, with total crossing capacity equal to the maximum flow.

Worked example

A network has source s, sink t, and two parallel paths: s→t directly with capacity 4, and s→a→t with capacities 6 and 2. Find the maximum flow from s to t.

4 … 6
Illustrated card showing 4 … 6
  1. 1Direct path s→t carries up to its capacity: 4 units.
  2. 2Path s→a→t is bottlenecked by the smaller edge capacity, min(6,2) = 2 units.
  3. 3Since the paths share no edges, total flow is the sum of both path flows.
  4. 4Total maximum flow = 4 + 2 = 6.

Answer: Maximum flow = 6

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students compute a cut's capacity by summing all edges crossing the partition in both directions; only edges directed from the source side to the sink side count towards cut capacity, so reverse-direction edges must be excluded.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard