Flow network explained

In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

Definition

A network is a directed graph with a non-negative capacity function for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we may assume that if, then is also a member of . Additionally, if then we may add to E and then set the .

If two nodes in are distinguished – one as the source and the other as the sink – then is called a flow network.^[1]

Flows

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.

The excess function represents the net flow entering a given node (i.e. the sum of the flows entering) and is defined by$$x\_f(u)=\backslash sum\_\; f(w,u).$$A node is said to be active if (i.e. the node consumes flow), deficient if (i.e. the node produces flow), or conserving if . In flow networks, the source is deficient, and the sink is active.Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

A pseudo-flow is a function of each edge in the network that satisfies the following two constraints for all nodes and :

• Skew symmetry constraint: The flow on an arc from to is equivalent to the negation of the flow on the arc from to, that is: . The sign of the flow indicates the flow's direction.

• Capacity constraint: An arc's flow cannot exceed its capacity, that is: .

A pre-flow is a pseudo-flow that, for all, satisfies the additional constraint:

• Non-deficient flows: The net flow entering the node is non-negative, except for the source, which "produces" flow. That is: for all .

A feasible flow, or just a flow, is a pseudo-flow that, for all, satisfies the additional constraint:

• Flow conservation constraint: The total net flow entering a node is zero for all nodes in the network except the source

s and the sink t , that is: for all

Notes and References

1. A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989