nrich
enriching mathematics
Skip over navigation
Home
Home
Students
Guide and features
Teachers
Guide and features
STEM
Science, Technology, Engineering and Mathematics
AskNRICH
Forum
early years
Featured Early Years Foundation Stage; US Kindergarten
Early years
primary
Featured UK Key Stage 1&2; US Grades 1-4
Primary teachers
secondary
Featured UK Key Stage 3-5; US Grades 5-12
Secondary teachers
primary lower
Featured UK Key Stage 1, US Grade 1 & 2
primary
primary
Featured UK Key Stage 2; US Grade 3 & 4
secondary lower
Featured UK Key Stages 3 & 4; US Grade 5-10
secondary
secondary upper
Featured UK Key Stage 4 & 5; US Grade 11 & 12
Topics
translate
Problem
Getting Started
Solution
Teachers' Resources
Printable page
Maximum Flow
Stage: 5
Challenge Level:
Warm-up
Try this next
Think higher
Read: mathematics
Read: science
Explore further
The graph represents a supply network from $A$ to $B$ and the numbers on the edges of the graph show the maximum capacity for flow in each of the sections.
Imagine any straight line cutting through edges of the graph (but not through vertices) such that $A$ is on one side of the line and $B$ is on the other. All the flow from $A$ to $B$ has to go along the edges cut by your line so the total flow from $A$ to $B$ is less than or equal to the sum of the flows along those edges. Considering all possible such cuts, why is it that the maximum flow from $A$ to $B$ is less than the minimum sum for all cuts? Find the maximum flow in this example.
In the second example the network is a cube. Find the maximum flow from $A$ to $G$.
biology
.
engineering
.
Mathematical modelling
.
physics
.
Optimisation
.
Flows in a network
.
Calculus generally
.
Maths Supporting SET
.
Networks/Graph Theory
.
Real world
.