The Network
Flows and Capacities
A flow network asks how much can physically get from a source to a sink when every directed edge has a pipe limit. The local constraints are simple, but they interact: a large incoming pipe is useless if the outgoing bottleneck is smaller. This lesson reads the network before any algorithm starts, so the later certificate has a concrete object to certify.
Network data
This network has 4 nodes and 5 directed edges. Think of the edges as pipes whose arrows fix the allowed direction of movement. Why: before we optimize anything, we need to know which routes can physically carry material from the source toward the sink and which routes simply do not exist in the model.
Capacity limit
The s to a edge has capacity 3, and the b to t edge has capacity 3. A capacity is a hard local ceiling: the algorithm may choose a smaller flow on an edge, but it may not push more than the edge permits. Why: a global flow is feasible only when every local pipe limit is respected at the same time.
Conservation
At internal nodes, inflow must equal outflow. The source is allowed to inject flow and the sink is allowed to absorb it, but the middle nodes only pass flow along. Why: this is what makes the value of the flow a source-to-sink quantity instead of a collection of unrelated edge labels.
Diagram note
The diagram shows capacities only; no flow has been pushed yet. It is a snapshot of the instance, not of a solution. The exact-core boundary is that every capacity label is an integer from the pinned network, while the graph layout is just for reading the arrows. Pixel positions are rounded for layout; every number shown is exact.