| # Network Flows LP and QP > Applications> Back | Networks | Next Network models Minimum cost network flow ## Network models ### What is a network? We return to the network model described here. We consider a network (directed graph) having nodes connected by directed arcs (ordered pairs ). We assume there is at most one arc from node to node , and no self-loops. We define the arc-node incidence matrix to be the matrix with coefficients if arc starts at node , if it ends there, and otherwise. Note that the column sums of are zero: .
| The figure shows the graph associated with the arc-node incidence matrix
### Flows A flow (of traffic, information, charge) is represented by a vector , and the {em total flow leaving node } is then . ## Minimum cost network flow The minimum cost network flow problem has the LP form where is the cost of flow through arc , provide upper and lower bounds on and is an external supply vector. This vector may have positive or negative components, as it represents supply and demand. We assume that , so that the total supply equals the total demand. The constraint represents the balance equations of the network. ### Maximum flow A more specific example is the max flow problem, where we seek to maximize the flow between node (the source) and node (the sink). It bears the form with .