💡 A network is a tuple $N=(V,A,c,s,t)$, where the following hold:

1. $(V,A)$ is a directed graph,
2. $s\in V$ is the source,
3. $t\in V\setminus \{s\}$ is the target and,
4. $c:A⟶{\mathbb{R}}_0^{+}$ is the capacity function.

💡 Let $N=(V,A,c,s,t)$ be a network. A flow in $N$ is a function $f:A⟶\mathbb{R}$ with the conditions

1. $0\le f(e)\le c(e)$ for all $e\in A$, the admissibility, and

2. for all $v\in V\setminus \{s,t\}$ it holds that

   $$\sum _{u\in V:(u,v)\in A}f(u,v)=\sum _{u\in V:(v,u)\in A}f(v,u)$$

   which is called the flow conservation.

The value of a flow $f$ is defined by

$$\text{val}(f)=\text{netoutflow}(s)=\sum _{u\in V:(s,u)\in A}f(s,u)-\sum _{u\in V:(u,s)\in A}f(u,s).$$

📌 The net inflow of the target equals the value of the flow, i.e.,

$$\text{netinflow}(t)=\sum _{u\in V:(u,t)\in A}f(u,t)-\sum _{u\in V:(t,u)\in A}f(t,u)=\text{val}(f).$$

💡 An $s$-$t$-cut for a network $(V,A,c,s,t)$ is a partition $(S,T)$ of $V$ (i.e., $S\cup T=V$ and $S\cap T=\varnothing$) with $s\in S$ and $t\in T$. The capacity of an $s$-$t$-cut $(S,T)$ is defined by

$$\text{cap}(S,T)=\sum _{(u,w)\in (S\times T)\cap A}c(u,w).$$

📌 Let $f$ be a flow and $(S,T)$ be an $s$-$t$-cut in a network $(V,A,c,s,t)$. It then holds that

$$\text{val}(f)\le \text{cap}(S,T).$$

📖 (Max-Flow-Min-Cut Theorem).

Every network $N=(V,A,c,s,t)$ fulfills

$$\underset{f\text{flow in N}}{\max }\text{val}(f)=\underset{(S,T)\text{s-t-cut in N}}{\min }\text{cap}(S,T).$$

💡 Let $N=(V,A,c,s,t)$ be a network without opposing edges and let $f$ be a flow in $N$. The residual network $N_f=(V,A_f,r_f,s,t)$ is defined as follows:

1. If $e\in A$ with $f(e)<c(e)$, then $e$ is also an edge in $A_f$ with $r_f(e)=c(e)-f(e)$.
2. If $e\in A$ with $f(e)>0$, then $e^{\text{opp}}$ is in $A_f$ with $r_f(e^{\text{opp}})=f(e).$
3. Only edges ad defined in points 1 and 2 are in $A_f$.

$r_f(e)$, $e\in A_f$, is called the residual capacity of edge $e$.

📖 A flow $f$ in a network $N$ is a maximal flow if and only if there does not exist a directed path from the source $s$ to the target $t$ in the residual network $N_f$. For every such maximum flow there does exist an $s$-$t$-cut $(S,T)$ with $\text{val}(f)=\text{cap}(S,T)$.

📖 If all capacities are integer values and at max as large as some $U$ and there are no opposing edges in a network then there exists an integer maximum flow that can be found in $O(mnU)$, where $n$ is the number of nodes and $m$ is the number of edges of the network.

💡 (Capacity-Scaling, Dinitz-Gabow, 1973).

If in a network all capacities are integers and at max as large as some $U$, then there exists an integer maximum flow, that can be found in $O(mn(1+\log U))$, where $n$ is the number of nodes and $m$ is the number of edges of the network.

💡 (Dynamic Trees, Sleator-Tarjan, 1983).

A maximal flow of a network can be found in $O(mn\log n)$, where $n$ is the number of nodes and $m$ is the number of edges of the network.

📌 The maximum size of a matching in a bipartite graph equals the value of a maximum flow in network $N$.

💡 Recall Menger’s Theorems:

By cleverly converting a graph to a network we can turn the connectivity problem into a max-flow problem:

• Edges:

  We split the undirected edges of the original graph into two opposing edges, both with capacity 1. If we now add new vertices $s$ and $t$ to some vertices $u,v$ of the original graph via one outgoing (in the case of $s$) and one incoming edge (in the case of $t)$, as shown in the picture. The value of a max-flow directly corresponds to the number of edge-disjoint $u$-$v$-paths.

  

• Nodes:

  We transform the graph to a network exactly the same way as before, only this time we also split any node $x$ of the original graph that is not $u$ or $v$ into $x_{\text{in}}$ and $x_{\text{out}}$ and add an extra edge from $x_{\text{in}}$ to $x_{\text{out}}$ with capacity $1$, as shown in the picture. The value of a max-flow equals the number of disjoint $u$-$v$-paths.