flow
On a digraph^{}, define a sink to be a vertex with outdegree zero and a source to be a vertex with indegree zero. Let $G$ be a digraph with nonnegative weights and with exactly one sink and exactly one source. A flow on $G$ is an assignment $f:E(G)\to \mathbb{R}$ of values to each edge of $G$ satisfying certain rules:

1.
For any edge $e$, we must have $0\le f(e)\le W(e)$ (where $W(e)$ is the weight of $e$).

2.
For any vertex $v$, excluding the source and the sink, let ${E}_{in}$ be the set of edges incident^{} to $v$ and let ${E}_{out}$ be the set of edges incident from $v$. Then we must have
$$\sum _{e\in {E}_{in}}f(e)=\sum _{e\in {E}_{out}}f(e).$$
Let ${E}_{source}$ be the edges incident from the source, and let ${E}_{sink}$ be the set of edges incident to the sink. If $f$ is a flow, then
$$\sum _{e\in {E}_{sink}}f(e)=\sum _{e\in {E}_{source}}f(e).$$ 
We will refer to this quantity as the amount of flow.
Note that a flow given by $f(e)=0$ trivially satisfies these conditions. We are typically more interested in maximum flows, where the amount of flow is maximized for a particular graph.
We may interpret a flow as a means of transmitting something through a network. Suppose we think of the edges in a graph as pipes, with the weights corresponding with the capacities of the pipes; we are pouring water into the system through the source and draining it through the sink. Then the first rule requires that we do not pump more water through a pipe than is possible, and the second rule requires that any water entering a junction of pipes must leave. Under this interpretation^{}, the maximum amount of flow corresponds to the maximum amount of water we could pump through this network.
Instead of water in pipes, one may think of electric charge in a network of conductors. Rule (2) above is one of Kirchoff’s two laws for such networks; the other says that the sum of the voltage drops around any circuit^{} is zero.
Title  flow 
Canonical name  Flow 
Date of creation  20130322 13:00:50 
Last modified on  20130322 13:00:50 
Owner  bgins (4516) 
Last modified by  bgins (4516) 
Numerical id  6 
Author  bgins (4516) 
Entry type  Definition 
Classification  msc 05C20 
Classification  msc 94C15 
Synonym  network flow 
Related topic  MaximumFlowMinimumCutTheorem 
Related topic  MaximumFlowminimumCutTheorem 
Defines  maximum flow 
Defines  source 
Defines  sink 
Defines  Kirchoff’s law 