Flow Conservation at a Node

Introduces the flow conservation constraint for directed networks: at every interior node, total flow in equals total flow out. Covers verification, solving for unknown arc flows, computing the value of a flow at the source or sink, and applying conservation across multiple nodes of a small network.

Step 1 of 157%

Tutorial

Flow Conservation at an Interior Node

A flow on a directed network assigns a nonnegative value $f(u,v) \ge 0$ to each arc $(u,v)$ , representing the amount of material sent along that arc. Two nodes are designated as the source $s$ (where flow originates) and the sink $t$ (where flow terminates). Every other node is called an interior node.

The flow conservation constraint states that at every interior node $v$ , the total flow entering $v$ equals the total flow leaving $v\!:$

\sum\limits_{u\,:\,(u,v)\in A} f(u,v) \;=\; \sum\limits_{w\,:\,(v,w)\in A} f(v,w).

Intuitively, material is neither created nor destroyed at an interior node -- whatever flows in must flow out.

For example, suppose node $v$ has two incoming arcs carrying $3$ and $5$ units, and two outgoing arcs carrying $4$ and $4$ units. Then

\text{inflow} = 3 + 5 = 8, \qquad \text{outflow} = 4 + 4 = 8,

so conservation holds at $v$ .