What is a flow network in graph terms?

Conditions

• The graph is directed.
• There is a source vertex $s$ and a sink vertex $t$.
• Each directed edge $(u, v)$ has an associated capacity $c(u,v)$.

Reasoning, step by step

1. Identify the graph as a directed graph $G(V, E)$.
2. Locate the two distinguished vertices: the source $s$ and the sink $t$.
3. Recognize that $V$ is the set of vertices and $E$ is the set of directed edges.
4. Note that every edge $(u, v)$ carries a capacity value $c(u,v)$.

Example

The video defines a flow network as a directed graph written as $G(V, E)$ with a source $s$ and a sink $t$, where each edge $(u, v)$ has a capacity given as $c(u,v)$.

Common misconceptions

• Assuming the graph is undirected; the definition explicitly requires a directed graph.
• Thinking capacity is a property of the vertices rather than the edges.
• Believing a flow network can have multiple sources or sinks without specifying them as a single $s$ and $t$ in this basic definition.

Watch the explanation

Explore next

• What does the notation $c(u,v)$ mean?
• Why does the order in $(u,v)$ matter?
• What is the difference between flow and capacity?