Directed Networks with Capacities and Costs

A directed network is a directed graph $G=(N,A)$ together with a capacity function $u\colon A \to [0,\infty).$ For each arc $(i,j)\in A,$ the value $u_{ij}\geq 0$ is called the capacity of the arc — the maximum amount of flow that may be sent from $i$ to $j$ along it.

We describe a network by listing its arcs together with their capacities. For example, the network

$$(1,2,4),\quad (1,3,7),\quad (2,3,2),\quad (2,4,5),\quad (3,4,3)$$

has $4$ nodes and $5$ arcs. The capacity of arc $(1,2)$ is $u_{12}=4,$ the capacity of arc $(1,3)$ is $u_{13}=7,$ and so on.

Given a node $i,$ the arcs leaving $i$ are the arcs of the form $(i,\,\cdot\,),$ and the arcs entering $i$ are the arcs of the form $(\,\cdot\,,i).$ For node $2$ in the network above, the arcs leaving are $(2,3)$ and $(2,4),$ and the only arc entering is $(1,2).$