# Flow Network
**A [[Graph#Weighted graph|weighted]] and [[Graph#Directed graph|directed]] graph whose edges have a notion of capacity and flow and contains a source and a sink.**
> [!Example] Flow Network
> A *flow network* $G=(V,E)$ is a *directed* graph in which each edge $e=(u,v)\in E$ has a *non-negative* function $c(u,v)$ representing its *capacity*.
>
> Additionally, two vertices are distinguished - a *source* $s$ and a *sink* $t$ - which only have outgoing and ingoing flows respectively.
![[FlowNetwork.svg|650]]
*A flow network graph; edges are labelled such that $f/c$ represents $f$ flow through an edge of $c$ capacity; this network has a flow of 19*
> [!Flow]
> A *flow* in a network $G$ is a non-negative function $f:E\rightarrow [0,\infty)$, which assigns a flow to every edge and satisfies:
> - the *capacity constraint* - for all edges $e=(u,v)\in E$, $f(u,v)\le c(u,v)$ i.e. the flow of an edge never exceeds its capacity
> - *flow conservation* - for all vertices $v\in V\setminus \{s,t\}$, $\sum_{(u,v)\in E}f(u,v)=\sum_{(u,v)\in E}f(u,v)$ i.e. the flow into a vertex is equal to the flow out of it, except with the source and the sink
> ***
> The *value* of a flow for a network is $|f|=\sum_{v:(s,v)\in E}f(s,v)=\sum_{v:(v,t)\in E}f(v,t)$ i.e. the flow leaving the source or the flow entering the sink
A common problem in optimisation theory involving flow networks is the [[maximum flow problem]].
## Residual network
The *residual network* of a flow network with some flow $f$ is the network constructed from the *remaining capacity* of the edges.
For every edge $(u, v)$ in the original network, the residual network consists of two edges:
- an edge $(u,v)$ with capacity $c(u,v) - f(u,v)$
- an edge $(v,u)$[^1] with capacity $f(u,v)$
The capacities of the edges of the residual network represent the *amount of additional flow* which could go through the edge.
![[FlowNetworkResidual.svg|550]]
### Augmenting path
An *augmenting path* is a path from the source to the sink in a *residual* network. A residual network may have multiple augmenting paths.
The capacity of an augmenting path is the capacity of the *bottleneck*, the edge with the lowest residual capacity.
![[FlowNetworkAugmenting.svg|550]]
*The above residual network with an augmenting path highlighted*
If *any* augmenting path exists within a flow network, then the flow $f$ from which the residual network was constructed is *not* the maximum flow.
However, maximum flow can be attained by continually *augmenting the flow*, which involves pushing additional units of flow equal to the capacity of the augmenting path through the path, until no more augmenting paths exist.
![[FlowNetworkAugmented.svg|550]]
*The above flow network with a 4 unit flow pushed through the augmenting path; the new flow is 23 units which is the maximum flow*
[^1]: Note the reversal of the flow.