What does the notation $c(u,v)$ mean in a flow network?

Conditions

• There is a directed edge from $u$ to $v$.
• Capacity is a quantitative attribute assigned to that specific edge.

Reasoning, step by step

1. Identify the directed edge $(u, v)$ in the graph.
2. Recognize $c(u,v)$ as the capacity function applied to this edge.
3. Understand that this value sets the upper limit for the flow on that edge.
4. Relate it to the physical analogy of a pipe's maximum water-carrying capacity.

Example

The speaker explains that each edge $(u, v)$ has a capacity given as $c(u,v)$, and uses a water-pipe analogy where the pipe corresponds to the edge and the amount of water it can carry corresponds to $c(u,v)$.

Common misconceptions

• Thinking $c(u,v)$ is the actual flow currently passing through the edge; it is the maximum limit.
• Assuming capacity is a property of the nodes $u$ or $v$ rather than the edge between them.
• Believing the capacity is the same in both directions for an undirected edge, whereas the definition specifies a directed edge $(u,v)$.

Watch the explanation

Explore next

• What is the difference between flow and capacity?
• How do you read the numbers on the edges of a flow network diagram?
• Why does the order in $(u,v)$ matter?