Resources For Teachers For Tutors For Students & Parents Pricing
Create Free Account
Year 12 Maths Standard 2 (2027) Network flow

Network Flow Concepts (Source, Sink, Cut)

20 practice questions 0 video lessons Theory + worked examples

Get to grips with network flow for NSW Year 12 Mathematics Standard 2. In this topic you read a directed network whose edges carry capacities, pick out the source (where flow only leaves) and the sink (where flow only arrives), and add the inflow and outflow at each vertex.

You will learn what a cut is and how to find its capacity by adding the edges that cross from the source side to the sink side — a core Standard 2 skill for modelling water pipes, traffic, power lines and delivery routes, and the foundation for maximum-flow problems later in the course.

Practice 20 questions
Practice questions

Every question with a fully worked solution.

Start practising
Create a free accountTrack your progress and save your work as you go.
Create free account

Theory

A flow network is a directed diagram whose edges carry capacities. This Year 12 Standard 2 (NSW) guide shows how to identify the source and sink, read edge capacities, add the inflow and outflow at a vertex, and find the capacity of a cut that separates the source side from the sink side.

A flow network is a directed diagram: each edge is an arrow that shows the allowed direction of flow, and the number on it is its capacity — the most that can pass along that edge (litres per minute, cars per hour, megabits per second, and so on).

The source \(S\) is the vertex where flow only leaves (inflow \(=0\), outflow \(>0\)); the sink \(T\) is where flow only arrives (outflow \(=0\), inflow \(>0\)). At any other vertex the inflow is the total capacity of the arrows pointing in and the outflow is the total capacity of the arrows pointing out.

A cut divides the vertices into two groups — one holding the source, the other holding the sink. Its capacity is the sum of the capacities of the edges directed from the source side to the sink side. Along any single path from \(S\) to \(T\), the flow can never exceed the smallest capacity on that path.

Directed flow networkSource S in green, sink T in red, capacities in Mbps on each arrow 12 7 4 8 10 S A B T
Source \(S\) (green), sink \(T\) (red); each arrow shows a capacity in Mbps.
A cut and its capacityCut separating S,A,B from T; the crossing edges are red 12 7 4 8 10 S A B T
The cut \(\{S,A,B\mid T\}\) crosses \(A\to T\) and \(B\to T\): capacity \(8+10=18\).

Inflow and outflow at a vertex \(v\) add up the capacities of its arrows:

\[\text{inflow}(v)=\sum(\text{capacities into }v),\qquad \text{outflow}(v)=\sum(\text{capacities out of }v)\]
inflow(v)=∑into

The source and sink are the special vertices:

\[\text{source }S:\ \text{inflow}=0,\quad \text{sink }T:\ \text{outflow}=0\]
source:inflow=0

The capacity of a cut adds only the forward-crossing edges (source side \(\to\) sink side):

\[\text{cut capacity}=\sum(\text{capacities of edges }S\text{-side}\to T\text{-side})\]
cut capacity=∑forward crossers
Flow along a path. The most that can travel along one path from \(S\) to \(T\) equals the smallest capacity on that path — the bottleneck edge.

How to read a flow network

  1. Find the source and sink. The source has no arrow pointing in; the sink has no arrow pointing out.
  2. Read a capacity straight off the arrow — the number is the maximum flow allowed in the arrow’s direction.
  3. Add inflow / outflow at a vertex by totalling the capacities of the arrows in / out.
  4. Capacity of a cut: split the vertices so \(S\) and \(T\) are on opposite sides, then add the capacities of the edges directed from the source side to the sink side (ignore any backward edge).
Example 1 — Source, sink and a capacity
The directed network shows stormwater drains (capacities in kL/h). Name the source and the sink, and give the capacity of the drain \(A\to T\).
Solution

The source has no arrow in; the sink has no arrow out.

Example 1 drainage networkSource S, sink T, capacities in kL per hour 9 6 7 5 S A B T
\(\text{inflow}(S)\)\(=\)\(0\)
\(\Rightarrow S\)\(\)\(\text{ is the source}\)
\(\text{outflow}(T)\)\(=\)\(0\)
\(\Rightarrow T\)\(\)\(\text{ is the sink}\)
\(\text{capacity }A\to T\)\(=\)\(7\ \text{kL/h}\)
S,T,7
Example 2 — Outflow, and flow along a path
A courier depot \(S\) sends parcels (parcels/h). Find the total outflow capacity at \(S\), and the greatest flow possible along the path \(S\to A\to T\).
Solution

Add the arrows leaving \(S\); a path is limited by its smallest capacity.

Example 2 courier networkCapacities in parcels per hour 10 8 5 6 9 S A B T
\(\text{outflow}(S)\)\(=\)\(10+8\)
\(\)\(=\)\(18\ \text{parcels/h}\)
\(\text{path }S\to A\to T\)\(=\)\(\min(10,6)\)
\(\)\(=\)\(6\ \text{parcels/h}\)
18,6
Example 3 — Capacity of a cut
For the power network (capacities in MW), the red edges form the cut separating \(\{S,A\}\) from \(\{B,T\}\). Find the capacity of this cut.
Solution

Add only the arrows directed from the source side to the sink side.

Example 3 power network with a cutCut S,A from B,T; crossing edges in red 14 9 3 6 11 S A B T
\(S\to B\)\(=\)\(9\)
\(A\to B\)\(=\)\(3\)
\(A\to T\)\(=\)\(6\)
\(\text{cut capacity}\)\(=\)\(9+3+6\)
\(\)\(=\)\(18\ \text{MW}\)
18
Example 4 — From a table, then a cut
A freight table lists directed links (containers/day): \(S\to A\ 7\), \(S\to B\ 4\), \(A\to B\ 3\), \(A\to T\ 6\), \(B\to T\ 8\). Name the sink and find the capacity of the cut separating \(\{S,A\}\) from \(\{B,T\}\).
Solution

Each row is an arrow From\(\to\)To; then add the forward crossers.

Example 4 freight network with a cutNetwork built from the table; cut edges in red 7 4 3 6 8 S A B T
\(\text{no arrow leaves }T\)\(\Rightarrow\)\(T\text{ is the sink}\)
\(\text{crossers}\)\(:\)\(S\to B,\ A\to B,\ A\to T\)
\(\text{cut capacity}\)\(=\)\(4+3+6\)
\(\)\(=\)\(13\ \text{containers/day}\)
13

Common pitfalls

Arrows are one-way. A directed edge \(S\to A\) allows flow only from \(S\) to \(A\); it does not let flow travel \(A\to S\).
Cuts count forward edges only. When you total a cut, add only the arrows crossing from the source side to the sink side — a backward arrow is not counted.
Capacity is a limit, not the flow. The number on an edge is the most it can carry; the flow along a whole path is capped by its smallest capacity.

Frequently asked questions

What is a source and a sink in a flow network?

The source is the vertex where flow only leaves, so no arrow points into it; the sink is the vertex where flow only arrives, so no arrow points out of it. In a diagram the source is usually shown in green and the sink in red.

How do you find the capacity of an edge?

Read the number printed on the arrow. It is the edge's capacity, meaning the maximum amount that can flow along it in the direction the arrow points. The units depend on the context, such as litres per minute or cars per hour.

What is a cut in a network?

A cut divides all the vertices into two groups so that the source is in one group and the sink is in the other. Every vertex belongs to exactly one side. Its purpose is to measure how much flow can cross from the source side to the sink side.

How do you calculate the capacity of a cut?

Add together the capacities of only the edges that are directed from the source side to the sink side. Edges that point backwards, from the sink side to the source side, are not included in the total.

What does inflow and outflow mean at a vertex?

Inflow is the total capacity of all the arrows pointing into a vertex, and outflow is the total capacity of all the arrows pointing out of it. The source has inflow zero and the sink has outflow zero.

Why can't flow along a path be more than the smallest capacity?

Every edge on the path is a limit, so the whole path can only carry as much as its weakest link. The smallest capacity on the path is the bottleneck, and no more than that amount can travel all the way from the source to the sink along it.

More in Network flow
Flow Capacity & Saturated Edges
20 questions
Maximum Flow - Minimum Cut
20 questions