flow

On a digraph, define a sink to be a vertex without-degree zero and a source to be a vertex within-degree zero.Let $G$ be a digraph with non-negative weights and with exactlyone sink and exactly one source.A flow on $G$ is an assignment$f:E(G)\to ℝ$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}$ bethe set of edges incident to $v$ and let $E_{out}$ be the set of edgesincident 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}$ bethe 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 amountof flow is maximized for a particular graph.

We may interpret a flow as a means of transmitting something througha network.Suppose we think of the edges in a graph as pipes, with the weightscorresponding with the capacities of the pipes; we are pouring waterinto the system through the source and draining it through the sink.Then the first rule requires that we do not pump more water througha pipe than is possible, and the second rule requires that any waterentering a junction of pipes must leave.Under this interpretation, the maximum amount of flow corresponds tothe 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 othersays that the sum of the voltage drops around any circuit is zero.

Title	flow
Canonical name	Flow
Date of creation	2013-03-22 13:00:50
Last modified on	2013-03-22 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