Network flow

L. El Ghaoui

Network flow

We describe a flow (of goods, traffic, charge, information, etc) across the network as a vector $x \in \mathbb{R}^{n}$ , which describes the amount flowing through any given arc. By convention, we use positive values when the flow is in the direction of the arc, and negative ones in the opposite case. The total flow leaving a given node $i$ is then (remember our convention that the index $j$ spans the arcs)

$\sum_{j=1}^{n} A_{ij}x_{j}=(Ax)_{i},$

with $(Ax)_{i}$ our notation for the $i$ -th component of vector $Ax$ . Now we define the external supply as a vector $b \in \mathbb{R}^{m}$ , with negative $b_{i}$ representing an external demand at node $i$ , and positive $b_{i}$ a supply. We assume that the total supply equals the total demand, which means $1^{T}b=0$ .

The balance equations for the supply vector $b$ are $Ax=b$ . These equations represent constraints the flow vector must satisfy in order to satisfy the external supply/demand represented by $b$ .

See also: Incidence matrix of a network.

Network flow

License

Share This Book