Imagine a network of water pipes connecting a reservoir to a city. The reservoir is the source, the city is the destination, and the pipes are the pathways. Each pipe has a maximum amount of water it can carry, its capacity. This entire system is a classic example of a flow network.

A flow network is a directed graph where each edge has a capacity. It's used to model scenarios where some material or data moves from a starting point (the source) to an ending point (the sink). Everything from supply chains and internet traffic to road systems can be represented as a flow network.

The key components are:

• Nodes (or Vertices): The points in the network, like pumping stations or routers.
• Edges: The directed connections between nodes, representing pipes or data cables.
• Source ($s$): The node where all flow originates. It only has outgoing edges.
• Sink ($t$): The node where all flow terminates. It only has incoming edges.
• Capacity ($c(u,v)$): A non-negative number associated with each edge $(u,v)$ that represents the maximum amount of flow that can pass through it.

Just having a network with capacities isn't enough. We need to define how stuff actually moves through it. This is called the flow, denoted by $f(u,v)$ for an edge from node $u$ to node $v$. A valid flow must follow two strict rules.

This is the capacity constraint. It's an intuitive rule: you can't push 15 gallons of water per second through a pipe built to handle only 10. For any two nodes $u$ and $v$, the flow must be between zero and the edge's capacity.

This is the rule of flow conservation. For any node in the network that is not the source or the sink, the total amount of flow entering the node must equal the total amount of flow leaving it. Nothing is created or lost at these intermediate points. They simply pass the flow along.

In this example, notice how node $u$ receives a flow of 8 from $s$. It then sends 5 to $t$ and 3 to $v$, for a total outgoing flow of 8. The flow is conserved. Likewise, node $v$ receives a total flow of 7 (4 from $s$ and 3 from $u$) and sends all 7 to $t$.

A central question in flow networks is: how much material is actually making it from the source to the sink? This is known as the value of the flow, often denoted as $|f|$.

We can calculate this value by measuring the total flow leaving the source. Since the source is where everything originates, the net amount it sends out is the total amount that enters the system.

Because a source node in a simple network has no incoming flow, the second term is zero. So, we just sum up the flow on all edges leaving $s$.

Alternatively, thanks to flow conservation, we could also measure the total flow arriving at the sink. The results will be the same.

In the network shown above, the total flow leaving source $s$ is $f(s,u) + f(s,v) = 8 + 4 = 12$. The total flow entering sink $t$ is $f(u,t) + f(v,t) = 5 + 7 = 12$. The value of this particular flow is 12.

Let's check your understanding of these fundamental concepts.

Understanding these basic properties—capacity constraints, flow conservation, and the value of a flow—is the first step. They form the foundation for solving more complex problems, like finding the maximum possible flow a network can handle.