# 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* ## Extensions ### Multiple sources and sinks Flow networks with multiple sources or sinks can be reduced to a flow network with a single source or sink. This can be done by adding a *super-source* or a *super-sink* that is connected to every source or sink, respectively, with *infinite capacity edges*. If there is a flow restraint on a source or a sink, an edge with capacity equal to the restraint can be used instead. ![[FlowNetworkMultiple.svg|600]] *A flow network with multiple sources and sink and a super-source and super-sink connected to them, respectively* ### Vertex capacities Flow networks with vertices that have capacities can be replaced with two vertices, an *in-vertex* that accepts the incoming edges to the vertex and an *out-vertex* that emits the outgoing edges. The two new vertices are connected by an edge with the capacity of the vertex while all incoming and outgoing edges preserve their original properties. ![[FlowNetworkVertexCapacities.svg]] [^1]: Note the reversal of the flow.