Flow network

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 road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

A network is a graph $G = (V, E)$ , together with a non-negative function $c : V \times V \to ℝ \infty$ , called the capacity function. Without loss of generality, it is assumed that if $(u, v) \in E$ then $(v, u)$ is also a member of $E$ , since if $(v, u) \notin E$ then $(v, u)$ may be added to E and then setting $c (v, u) = 0$ .

If two nodes in $G$ are distinguished, a source $s$ and a sink $t$ , then $(G, c, s, t)$ is called a flow network.

There are various notions of a flow function that can be defined in a flow graph. 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 simplest example of a flow function is known as a pseudo-flow.

Given a pseudo-flow $f$ in a flow network, it is often useful to consider the net flow entering a given node $v$ , that is, the sum of the flows entering $v$ . The excess function $x f : V \to ℝ$ is defined by $x f (u) = \sum v \in V f (v, u)$ . A node $u$ is said to be active if $x f (u) > 0$ , deficient if $x f (u) < 0$ or conserving if $x f (u) = 0$ .

...
Wikipedia