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 incidence matrix of the network, denoted by A, helps represent the relationship between nodes and arcs. For a given node i, the total flow leaving it can be calculated as (remember our convention that the index j spans the arcs)

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

where (Ax)_{i} is our notation for the i-th component of vector Ax.

Now, we define the external supply as a vector b \in \mathbb{R}^{m}. Here, a negative b_{i} represents an external demand at node i, and a positive b_{i} denotes a supply. We make the assumption that the total supply equals the total demand, implying

    \[ 1^{T}b = 0. \]

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

See also: Incidence matrix of a network.

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Linear Algebra and Applications Copyright © 2023 by VinUiversity is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, except where otherwise noted.

Share This Book