## You are here

Homeflow

## Primary tabs

# flow

On a digraph, define a *sink* to be a vertex with
out-degree zero and a *source* to be a vertex with
in-degree zero.
Let $G$ be a digraph with non-negative weights and with exactly
one sink and exactly one source.
A *flow* on $G$ is an assignment
$f:E(G)\rightarrow\mathbb{R}$
of values to each edge of $G$ satisfying certain rules:

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

2.

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.

## Mathematics Subject Classification

05C20*no label found*94C15

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections