Finite integral networks, feasible flows, values, cuts and residual networks

A finite integral $s$-$t$ network is a tuple $\mathcal{N}=(V,A,\mathrm{tail},\mathrm{head},s,t,c)$ where $V$ and the labelled arc set $A$ are finite, $s,t\in V$ are distinct, $\mathrm{tail},\mathrm{head}:A⟶V,$ every arc $a\in A$ has $\mathrm{tail}(a)\mathrm{\ne }\mathrm{head}(a)$, $c:A\to \mathbb{N}$, no arc enters $s$, and no arc leaves $t$. Parallel and antiparallel arcs are allowed because distinct elements of $A$ remain distinct.

A feasible integral flow is $f:A\to \mathbb{N}$ with $0\le f(a)\le c(a)$ and ${\sum }_{\mathrm{tail}(a)=v}f(a)={\sum }_{\mathrm{head}(a)=v}f(a)(v\in V\setminus \{s,t\})\mathrm{.}$ Its value is $\mathrm{\mid }f\mathrm{\mid }:={\sum }_{\mathrm{tail}(a)=s}f(a)$. An $s$-$t$ cut is a set $S\subseteq V$ with $s\in S$, $t\mathrm{\notin }S$; its capacity is $c(S):={\sum }_{\mathrm{tail}(a)\in S,\mathrm{head}(a)\mathrm{\notin }S}c(a)$.

The residual network of $f$ has the labelled copies $R_f=\{(a,+):f(a)<c(a)\}\cup \{(a,-):f(a)>0\}\mathrm{.}$ On these copies, put $\begin{array}{rlrlrl}{\displaystyle {\mathrm{tail}}_f(a,+)}& {\displaystyle =\mathrm{tail}(a),}& {\displaystyle {\mathrm{head}}_f(a,+)}& {\displaystyle =\mathrm{head}(a),}& {\displaystyle r_f(a,+)}& {\displaystyle =c(a)-f(a),}\\ {\displaystyle {\mathrm{tail}}_f(a,-)}& {\displaystyle =\mathrm{head}(a),}& {\displaystyle {\mathrm{head}}_f(a,-)}& {\displaystyle =\mathrm{tail}(a),}& {\displaystyle r_f(a,-)}& {\displaystyle =f(a)\mathrm{.}}\end{array}$ For $x,y\in V$, an $x$-$y$ residual path is a sequence ${\rho }_1,\dots ,{\rho }_k$ of members of $R_f$, with $k\ge 1$, for which ${\mathrm{tail}}_f({\rho }_1)=x,{\mathrm{head}}_f({\rho }_k)=y,{\mathrm{head}}_f({\rho }_i)={\mathrm{tail}}_f({\rho }_{i+1})(1\le i<k),$ and the vertex list $x,{\mathrm{head}}_f({\rho }_1),\dots ,{\mathrm{head}}_f({\rho }_k)=y$ has no repetitions. Thus the path records the selected labelled copies, so $(a,-)$ never coincides with a forward copy of an antiparallel original arc.

• Capacities and flows are natural numbers here. No rational, real, or infinite-capacity termination assertion is part of this definition.