Network Flows, Conservation and Cycles

Definition A directed graph consists of nodes, numbered $1, \dots, n$, and edges, numbered $1, \dots, m$. Each edge joins two different nodes and carries an arrow from one to the other, its reference direction. In a flow network, edge $k$ carries a real number $f_k$, its flow, measured along the arrow, and the flows form a column $\mathbf{f}$ in $\mathbb{R}^m$. A positive $f_k$ means material moves along the arrow, and a negative $f_k$ means it moves against the arrow at the rate $\lvert f_k \rvert$. Whether negative flows are physically possible is a separate modeling decision. The graph is connected when any two nodes are joined by a chain of edges, with the arrows ignored.

Definition The incidence matrix of a directed graph with $n$ nodes and $m$ edges is the $n \times m$ matrix $B$ with entries

Rows belong to nodes and columns to edges. Each column has exactly one entry $1$ and one entry $-1$, so every column sums to zero. As a matrix, $B$ maps $\mathbb{R}^m$ to $\mathbb{R}^n$, and entry $i$ of $B\mathbf{f}$ is the total flow leaving node $i$ minus the total flow entering it, with flows counted with their signs. If the graph is connected, then $\operatorname{rank} B = n - 1$. Indeed, for an edge $k$ from $i$ to $j$, entry $k$ of $B^{\top}\mathbf{y}$ is $y_i - y_j$. So $B^{\top}\mathbf{y} = \mathbf{0}$ forces equal values at the two ends of every edge, hence at all nodes of a connected graph. The null space of $B^{\top}$ is therefore the line spanned by the all-ones vector $\mathbf{1} = (1, \dots, 1)$ in $\mathbb{R}^n$, and $\operatorname{rank} B = n - \dim \operatorname{Null} B^{\top} = n - 1$.

Definition The net supply $s_i$ of node $i$ is the rate at which material enters the network from outside at that node. A positive $s_i$ is a source, a negative $s_i$ is consumption, and $s_i = 0$ means the node only passes material on. Assume a steady state, with no storage at the nodes and no loss along the edges. Conservation at node $i$ then says that the sum of the flows on edges leaving node $i$, minus the sum of the flows on edges entering it, equals $s_i$. With the supply vector $\mathbf{s} = (s_1, \dots, s_n)$, the conservation equations at all nodes form the single system

with $n$ equations in $m$ unknowns. Its solutions are the flows compatible with the supplies. If $\mathbf{f}_0$ is one of them, then they are exactly the vectors $\mathbf{f}_0 + \mathbf{z}$ with $\mathbf{z}$ in $\operatorname{Null} B$.

Definition A cycle is a closed route through the graph that starts and ends at the same node, uses each edge at most once and passes through no node twice apart from its return to the start. The route may use an edge along or against its arrow. Choose a direction of travel. The circulation around the cycle is the vector $\mathbf{c}$ in $\mathbb{R}^m$ with $c_k = 1$ if the route uses edge $k$ along its arrow, $c_k = -1$ if it uses edge $k$ against its arrow, and $c_k = 0$ if it does not use edge $k$. Then $B\mathbf{c} = \mathbf{0}$, because at each node of the route the edge used to arrive contributes $-1$ and the edge used to leave contributes $+1$, whichever way their arrows point. Hence $\mathbf{f} + \alpha\mathbf{c}$ has the same net supplies as $\mathbf{f}$ for every real $\alpha$. For a connected graph, rank-nullity gives

and $\operatorname{Null} B$ is spanned by circulations around cycles.

Definition If each edge can carry material only along its arrow, as in a one-way pipe or street, the model adds the inequalities $f_k \ge 0$ for every edge $k$, written $\mathbf{f} \ge \mathbf{0}$. A flow is feasible when it satisfies both $B\mathbf{f} = \mathbf{s}$ and $\mathbf{f} \ge \mathbf{0}$. The inequalities are an extra requirement of the model, not a consequence of the linear system. The feasible set is the part of the solution set of $B\mathbf{f} = \mathbf{s}$ in which every entry is nonnegative. If $\mathbf{f}$ and $\mathbf{g}$ are feasible, so is every flow $(1 - \lambda)\mathbf{f} + \lambda\mathbf{g}$ with $0 \le \lambda \le 1$ between them, but the feasible set is a subspace only in the trivial case where it is $\{\mathbf{0}\}$. When $\mathbf{s} \ne \mathbf{0}$ it does not contain $\mathbf{0}$, and when it contains a nonzero $\mathbf{f}$ it does not contain $-\mathbf{f}$, which has a negative entry. It can be a single point, a bounded segment, an unbounded set, or empty even when $B\mathbf{f} = \mathbf{s}$ has solutions.

Definition Every column of $B$ sums to zero, so $\mathbf{1}^{\top}B = \mathbf{0}^{\top}$. For every flow the entries of $B\mathbf{f}$ therefore add to $\mathbf{1}^{\top}B\mathbf{f} = 0$, and the system $B\mathbf{f} = \mathbf{s}$ can have a solution only if

For a connected graph with signed flows the condition is also sufficient. A vector lies in $\operatorname{Col} B$ exactly when it is orthogonal to $\operatorname{Null} B^{\top}$, and that null space is spanned by $\mathbf{1}$. If the graph splits into several connected pieces with no edges between them, the supplies must add to zero on each piece separately. Under the constraint $\mathbf{f} \ge \mathbf{0}$ the condition is still necessary but no longer sufficient in general, as the example below shows.