Network flow

We describe a flow (of goods, traffic, charge, information, etc.) across the network as a vector , 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 incidence matrix of the network, denoted by , helps represent the relationship between nodes and arcs. For a given node , the total flow leaving it can be calculated as (remember our convention that the index spans the arcs)

where is our notation for the th component of vector .

Now, we define the external supply as a vector . Here, a negative represents an external demand at node , and a positive denotes a supply. We make the assumption that the total supply equals the total demand, implying

The balance equations for the supply vector are given by . These equations represent constraints the flow vector must satisfy to meet the external supply/demand represented by .

See also: Incidence matrix of a network.